洛谷 P2796 Facer的程序 题解

题面

一个树形DP，

f[i]=表示以i为根可以得到的子树个数；

则f[i]*=(f[j]+1)；

初始化f[i]=1;

ans=sigma(f[i]);

#include <bits/stdc++.h>

#define p 1000000007

using namespace std;

struct littlestar{

    int to;

    int nxt;

}star[];

int head[],cnt;

void add(int u,int v)

{

    star[++cnt].to=v;

    star[cnt].nxt=head[u];

    head[u]=cnt;

}

long long f[];

void dfs(int u,int fa)

{

    for(int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        dfs(v,u);

        f[u]=(f[u]*(f[v]+))%p;

    }

}

signed main()

{

    int n;

    cin>>n;

    for(int i=;i<=n;i++) f[i]=;

    for(int i=;i<=n-;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v);

        add(v,u);

    }

    dfs(,);

    long long ans=;

    for(int i=;i<=n;i++){

        ans=(ans+f[i])%p;

    }

    cout<<ans%p;

    return ;

}