P2796 Facer的程序

P2796 Facer的程序

比较简单的树形DP，求树上子树个数。

对于一个节点 $x$ ，在每一个子节点 $y$ 都有 $f[y] + 1$ 种选法。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7;
int n;
LL f[N];
int idx, hd[N], nxt[M], edg[M];
void dfs(int x, int fa)
{
    f[x] = 1;
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != fa)
        {
            dfs(edg[i], x);
            f[x] = f[x] * (f[edg[i]] + 1) % mod;
        }
}
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1, a, b; i < n; i++)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs(1, 0);
    LL res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + f[i]) % mod;
    printf("%lld", res);
    return 0;
}