CodeForces 543D 樹形DP Road Improvement

題意：

有一顆樹，每條邊是好邊或者是壞邊，對于一個節點為x，如果任意一個點到x的路徑上的壞邊不超過1條，那么這樣的方案是合法的，求所有合法的方案數。

對于n個所有可能的x，輸出n個答案。

分析：

題解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 200000 + 10;
const int MOD = 1000000007;
int n;

vector<int> G[maxn], pre[maxn], suf[maxn];

void scan(int& x)
{
    x = 0;
    char c = ' ';
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
}

int d[maxn], f[maxn];

void mul(int& x, int y) { x = 1LL * x * y % MOD; }

void dfs(int u)
{
    d[u] = 1;
    int sz = G[u].size();
    for(int i = 0; i < sz; i++)
    {
        int v = G[u][i];
        dfs(v);
        mul(d[u], d[v] + 1);
    }

    int p = 1, s = 1;
    for(int i = 0; i < sz; i++)
    {
        mul(p, d[G[u][i]] + 1);
        mul(s, d[G[u][sz-1-i]] + 1);
        pre[u].push_back(p);
        suf[u].push_back(s);
    }

    reverse(suf[u].begin(), suf[u].end());
}

void dfs2(int u)
{
    int sz = G[u].size();
    for(int i = 0; i < sz; i++)
    {
        int v = G[u][i];
        f[v] = f[u];
        if(i > 0) mul(f[v], pre[u][i - 1]);
        if(i < sz - 1) mul(f[v], suf[u][i + 1]);
        f[v]++;
        if(f[v] >= MOD) f[v] -= MOD;
        dfs2(v);
    }
}

int main()
{
    scanf("%d", &n);
    for(int x, i = 2; i <= n; i++)
    {
        scan(x);
        G[x].push_back(i);
    }

    dfs(1);
    f[1] = 1;
    dfs2(1);

    for(int i = 1; i <= n; i++) printf("%I64d ", 1LL * d[i] * f[i] % MOD);

    return 0;
}

?