题解 P2796 【Facer的程序】

· · 题解

Solution:

定义:以1号节点为根

定义:f[i]为以节点i为根的子树个数

边界:f[i]=1\ \ \ \ \ \ (\text{节点i为叶子节点}

转移:\large{}f[i]=\Large\prod\limits_{j\text{是i的子节点}}(f[j]+1)

推理:对于状态f[i],i节点自身一定是要选的，而对于它的子节点为根的子树，有f[j]种方案，显然这颗子树也可以不选，所以有(f[j]+1)种选法，根据乘法原理，总方案数为它们的乘积，即\prod\limits_{}(f[j]+1)

答案:\sum\limits_{i=1}^nf[i]

Code: 
#include<bits/stdc++.h>
#define p 1000000007
using namespace std;
typedef long long ll;
int n,h[100005],tot=0;
struct edge{
    int to,next;
}e[200005];
void add(int x,int y){
    e[++tot].to=y;e[tot].next=h[x];h[x]=tot;
}
int f[100005],ans=0;
void dfs(int x,int fa){
    f[x]=1;
    for(int i=h[x];i;i=e[i].next)
      if(e[i].to!=fa)
        dfs(e[i].to,x),f[x]=(ll)((ll)f[x]*f[e[i].to]+f[x])%p;
    ans+=f[x];ans%=p;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}