一棵树的子树数量

子树数量"/>

一棵树的子树数量

原题：Who killed Cock Robin

题意：

给出一颗无根树，问有多少种子图（包括点）

解析：

既然无根树，那么就随便选择一个点为rt，就1好了

用x[i]表示以i点为父亲得到的图的可能性
对于每个点i，儿子数为0时，x[i]为0，有n个儿子时，对于每个儿子j所能产生的可能性为x[j]+1，而x[i]为随便选任意个儿子相乘之和

eg：有三个儿子可能性为2 3 4，可能得到的就是3 4 5
那么x[i]=3+4+5+3*4+4*5+3*5+3*4*5

任意乘有个公式：dp[i]=dp[i-1]*x[i]+x[i] （dp[i]为前i个数的任意乘）
因为3和4有3，4，3*4，加入5多了5，3*5，4*5，3*4*5，多了的部分就是5*前面部分加一个5

另外，x[儿子]和x[父亲]都要加到ans里面，因为以父亲为root的那部分是从父亲开始往下延的，而x[儿子]是以儿子为root的

代码：

#define N 100009
int n;
vector<int>v[2*N];
D Ans=0;D fin(int ar,int fa){int haveson=0;queue<D>Q;for(int i=0;i<v[ar].size();i++){if(v[ar][i]==fa)continue;D add=fin(v[ar][i],ar)+1;Q.push(add);}D ans=0;while(!Q.empty()){ans+=ans*Q.front()%mod;ans=(ans+Q.front())%mod;Q.pop();}Ans=(Ans+ans)%mod;return ans;
}int main(){cin>>n;Ans+=n;for(int i=1;i<=n-1;i++){int a,b;scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}fin(1,0);printf("%lld\n",Ans);
}