【题意】给定n+1个点的树（root=0），每个点可以选择放或不放弹珠，每一轮顺序进行以下操作：
1.将根节点0的弹珠加入答案。
2.每个点的弹珠移向父亲。
3.如果一个点有超过2个弹珠，全部丢掉。
如果树中仍有弹珠，继续下一轮。
共有2^(n+1)种放弹珠的方案，计算所有方案的答案之和，取模1e9+7。
n<=2*10^5。（部分分：n<=2*10^3）
【算法】树形DP
【题解】容易发现，层与层之间互相独立，第i轮只需要考虑第i层的节点组合的子集中有多少个子集能到达0点，加起来就是总答案。
接下来考虑每轮进行一次树形DP，为了方便求解集合交，将方案计算转化为概率计算（集合交就是概率的乘积），则每个点有弹珠的概率是1/2。
令f[i][j]表示节点i有j个弹珠(j=0,1)的概率，则有：
f[i][1]=Σs/f[j][0]*f[j][1]，s=Πf[j][0]，j=son(i)
f[i][0]=1-f[i][1]
每一轮将对应深度的点全部初始化为1/2，然后树形DP到根就可以得到答案，复杂度O(n^2)，400分。
考虑将一个点在多轮的情况都考虑起来，f[i][d][j]表示点i在第d轮有j个弹珠的概率（j=0,1,2，2代表>=2）。
令f[i][d]={f[i][d][0],f[i][d][1],f[i][d][2]}，即视为一个状态，对于同轮（同深度同d）的两个状态可以合并（两个状态对应9种交集，交集乘 后 并集加）
对于一个点要将其所有儿子合并，两个点合并只需将0~min(d1,d2)的状态对应合并，以d大的点作为基础来合并（不要复制）。
那么初始状态为f[i][0]={1/2,1/2,0}，对于每个点将其儿子全部合并，然后顺推一位将d=0设为初始状态，最后记得将状态中的2搬到0处，注意这个过程必须只搬有改动的状态才能保证复杂度（之前不能直接归为0是因为在儿子的合并中2和0有区别）
复杂度分析同线段树合并，O(n)。
唔……真的挺难说清楚的，推荐原题解Editorial，把这篇当作简单的翻译就好了。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=,MOD=;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
struct cyc{
int z0,z1,z2;
};
cyc operator + (cyc a,cyc b){
cyc c;
c.z0=1ll*a.z0*b.z0%MOD;
c.z1=(1ll*a.z0*b.z1+1ll*a.z1*b.z0)%MOD;
c.z2=(1ll*a.z0*b.z2+1ll*a.z2*b.z0+1ll*a.z1*b.z1+1ll*a.z2*b.z2+1ll*a.z1*b.z2+1ll*a.z2*b.z1)%MOD;
return c;
}
vector<cyc>a[maxn];
int n,fa[maxn],first[maxn],cnt=,tot=,b[maxn];
struct edge{int v,from;}e[maxn*];
void insert(int u,int v){cnt++;e[cnt].v=v;e[cnt].from=first[u];first[u]=cnt;}
int MO(int x){return x>=MOD?x-MOD:x;}
void merge(int &x,int y){
if(a[x].size()<a[y].size())swap(x,y);
for(int i=;i<(int)a[y].size();i++){
a[x][a[x].size()-i-]=a[x][a[x].size()-i-]+a[y][a[y].size()-i-];
}
}
int main(){
n=read()+;
for(int i=;i<=n;i++)fa[i]=read()+,insert(fa[i],i);
for(int i=n;i>=;i--){
int mx=;
if(!first[i]){
a[b[i]=++tot].push_back((cyc){(MOD+)/,(MOD+)/,});
}
else{
b[i]=b[e[first[i]].v];
for(int j=e[first[i]].from;j;j=e[j].from){
mx=max(mx,min((int)a[b[i]].size(),(int)a[b[e[j].v]].size()));
merge(b[i],b[e[j].v]);
}
a[b[i]].push_back((cyc){(MOD+)/,(MOD+)/,});
}
for(int j=(int)a[b[i]].size()--;j>=(int)a[b[i]].size()-mx-;j--)a[b[i]][j].z0+=a[b[i]][j].z2,a[b[i]][j].z2=;
}
int ans=,N=;
for(int i=;i<=n;i++)N=(N<<)%MOD;
for(int i=;i<(int)a[b[]].size();i++)ans=MO(ans+1ll*a[b[]][i].z1*N%MOD);
printf("%d",ans);
return ;
}