题解 P5007 【DDOSvoid 的疑惑】

DDOSvoid · 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

subtask 3：

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

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

时间复杂度依然是 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;
}