题面 首先可以发现以0为根时，层与层之间时独立的，于是就有了一种O(n^2)的做法：对每一层DP一次，设f[d][i][0/1]表示当前考虑第d层的贡献，i的子树中贡献0/1的方案数。那么最后我们得到很多f[][0][0/1]，然后问题就变成从每个f[d][0][0/1]只能选其一，选中的数相乘并乘上选的f[][0][1]的个数再求总和，随便计数一下就好。 接着我们考虑怎么把这么所有层放在一起DP，我们重新定义一下状态f[d][i][0/1/2]表示考虑i下面的第d层，使得i上有0/1/多个的方案数。就是一个点i有一串dp状态。 然后就有一种类似启发式合并的做法，父亲先继承下状态最多的那个儿子，然后合并其他儿子的答案。 其实这样合并是O(n)的。因为同一层的两个点u,v只会在其LCA合并一次，然后同层所有点两两的LCA最多有该层点数-1个（很容易证）。所以总合并次数是O(n)级别的。 注意写的时候不能对状态最多的那个儿子做任何遍历之类的操作，否则复杂度GG。 代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #define ll long long #define pll pair<ll,ll> using namespace std; const int maxn=200010; const int mod=1000000007; int n,id[maxn],d[maxn],num; ll mor[maxn]; vector<pll > f[maxn]; struct edge { int t; edge *next; }*con[maxn]; void ins(int x,int y) { edge *p=new edge; p->t=y; p->next=con[x]; con[x]=p; } void dp(int v,int fa) { int mx=n+1; for(edge *p=con[v];p;p=p->next) if(p->t!=fa) { dp(p->t,v); if(d[p->t]>d[mx]) mx=p->t; } if(mx<=n) id[v]=id[mx],d[v]=d[mx]+1; else id[v]=++num; f[id[v]].push_back(make_pair(1,1)); bool flag=0; for(edge *p=con[v];p;p=p->next) if(p->t!=fa&&p->t!=mx) { flag=1; for(int i=d[v]-d[p->t]-1;i<d[v];i++) { pll t=f[id[p->t]][i-d[v]+d[p->t]+1]; mor[i]=(mor[i]*(t.first+t.second)%mod+f[id[v]][i].second*t.second%mod)%mod; f[id[v]][i].second=(f[id[v]][i].second*t.first%mod+f[id[v]][i].first*t.second%mod)%mod; f[id[v]][i].first=f[id[v]][i].first*t.first%mod; } } if(flag) for(int i=0;i<d[v];i++) f[id[v]][i].first=(f[id[v]][i].first+mor[i])%mod,mor[i]=0; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); ins(i,x); ins(x,i); } d[n+1]=-1; dp(0,-1); ll tot=1,sum=0; for(int i=0;i<=d[0];i++) { int sz=(f[id[0]][i].first+f[id[0]][i].second)%mod; sum=(sum*sz%mod+f[id[0]][i].second*tot%mod)%mod; tot=tot*sz%mod; } printf("%lld",sum); return 0; }