HDU5647 DZY Loves Connecting 树形DP
（先奉上jcvb大神的官方题解）BC 76 div 1 1002
对于每个结点i，统计出f[i]表示包含i的连通集有多少个，那么容易看出答案就是所有f[i]的和。
要计算f[i]是经典的树形DP问题。令g[i]表示以i为根的连通集的数目，那么g[i]=∏(g[j]+1)，
j是i的儿子，按这个从下往上DP一遍。
然后再用同样的式子从上往下DP一遍就好了。这一步骤写的时候要注意一下不要写错。
时间复杂度O(n)。
然后本蒟蒻不会这么写，因为一些人说需要逆元，而且这个题卡逆元，所以果断没有写
然后果断看了rank1的代码，然后写了一发，A掉了
蒟蒻大体说一下rank1的思路，看了半天请教学长才会
分析：题意是无根树，然后把它转化成有根树，这样每一个联通集都有一个跟节点
下面来定义g[i]代表以 i 为根节点的联通集的方案数，
f[i]代表以 i 为根节点的每个方案的大小之和
然后可见 ans就是所有f[i]的数量和
注：（这里的g[i]与官方题解一样，f[i]是不一样的）
代码：
#include <stdio.h> #include <cstring> #include <iostream> using namespace std; typedef long long LL; const int N=2e5+5; const LL mod=1e9+7; LL g[N],f[N],ans; int T,n,head[N],tot; struct Edge{ int v,next; }edge[N<<1]; void add(int u,int v){ edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++; } void dfs(int u,int fa){ f[u]=g[u]=1; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==fa)continue; dfs(v,u);//处理子节点 f[u]=(f[u]*(g[v]+1)%mod+g[u]*f[v]%mod)%mod; //处理到当前子节点分支，如何得到当前f[u] //进行分治，讨论连通集是否包含这个新分支中的点 //这就是上面的式子，我就是分治理解的 g[u]=g[u]*(g[v]+1)%mod; //得到当前子节点的以u为根的方案数 } ans=(ans+f[u])%mod; } int main() { scanf("%d",&T); while(T--){ scanf("%d",&n); ans=tot=0; for(int i=1;i<=n;++i)head[i]=-1; for(int i=2;i<=n;++i){ int v; scanf("%d",&v); add(i,v),add(v,i); } dfs(1,0); printf("%I64d ",ans); } return 0; }