P17169【FDOI R2 T1】过去

Circle_Table · 2026-07-20 11:17:27 · 题解

题目传送门

欢迎来博客园阅读！

验题人题解。

:::info[非负二元权值] 翻译成人话是数据范围中的那句 0 \leq w_i \leq 1。

题意

一棵由 n 个点组成的树，每个节点的权值 w_i \in \{0,1\}，求所有包含节点 1 的连通点集的权值之和。

本题解中称连通点集 S 的权值为 val。

思路

注意到每个节点的权值 w_i \in \{0,1\}，由此可以推出一个节点选与不选之间是相差 1 的。

由此，我们可以通过增减选出的 1 的个数来改变连通点集的权值。由于每次增减的是 1，不难发现我们可以取到的 val 具有连续性。因此我们求出 val 的最大值和最小值 val_{\min},val_{\max} 后看两者之间有多少个数就可以了。

考虑怎么求这两个东西。

• 最小值就是只取一个点，也就是 val_{\min}=w_1；
• 由于 w_i \in \{0,1\} 非负，最大值就应该是总权值之和，也就是 val_{\max}=\sum_{i=1}^{n}w_i。

最终不同的权值集合就是 \{val \in \mathbb{N}\mid val_{\min} \leq val \leq val_{\max}\}，答案为 val_{\max}-val_{\min}+1。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
int n,w,w1,sumw;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    cin>>w1,sumw+=w1;
    for(int i=2;i<=n;i++)cin>>w,sumw+=w;
    /* 与边无关，这一段可加可不加
    int u,v;
    for(int i=1;i<n;i++)cin>>u>>v;
    */
    cout<<sumw-w1+1<<'\n';
    return 0;
}

:::

完结撒花！