自动搬运

查看原文

来自洛谷，原作者为

	DDOSvoid **

搬运于2025-08-24 22:06:07，当前版本为作者最后更新于2018-11-05 18:57:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution：

subtask 1:

直接 $2^n$ 枚举子集即可

subtask 2：

定义 $f_i$ 为 i 的子树内的集合个数。

考虑如果 $i$ 只有两个儿子 $v_1$ 和 $v_2$，那么 $f_i=f_{v_1}*f_{b_2}+f_{v_1}+f_{v_2}+1$

这个非常显然。考虑如果有多个儿子，我们定义 $g_j$ 为前 $j$ 个儿子的集合个数，那么如果新加入一个儿子 $v$，$g_{j+1}=g_j*f_v+g_j+f_v$

$g_j$ 只和 $g_{j-1}$ 有关，所以直接开俩变量记录即可

复杂度 $O(n)$

subtask 3：

其实跟点权为 1 的情况类似

定义 $f_i$ 为 i 的子树内所有的毒瘤集的价值之和

$g_i$ 为 i 的子树内的毒瘤集的个数

转移与上面类似 v 为 u 的儿子

$f_u=f_u*g_v+f_v*g_u+f_u+g_u$

$g_u=g_u*g_v+g_u+g_v$

时间复杂度依然是 $O(n)$

别忘了模数是 1e8 + 7

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#define maxn 1000010
#define ll long long
#define gc getchar
using namespace std;

int n, m, T;

int w[maxn];

const int p = 100000007;

int read(){
    int x = 0; char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)){x = x * 10 + c - '0'; c = gc();}
    return x;
}

struct Edge{
    int to, next;   
}e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v){
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

ll f[maxn], g[maxn];
void dfs(int u, int fa){
    for(int i = head[u]; ~i; i = e[i].next){
        int v = e[i].to; if(v == fa) continue;
        dfs(v, u);
        f[u] = (f[u] * g[v] + f[v] * g[u] + f[u] + f[v]) % p;
        g[u] = (g[u] * g[v] + g[u] + g[v]) % p;
    }
    f[u] = (f[u] + w[u]) % p; ++g[u];
}

int main(){
    memset(head, -1, sizeof head);
    n = read(); T = read();
    for(int i = 1; i <= n; ++i) w[i] = T ? i : 1;
    for(int i = 1; i < n; ++i){
    	int x = read(), y = read();
        add_edge(x, y); add_edge(y, x); 	
    }
    dfs(1, 0); cout << f[1] << endl;
    return 0;
}