题目描述：
Sunke有一棵N + 1个点的树，其中0为根，每个点上有0或1个石子，Sunke会不停的进行如下操作直至整棵树没有石子：
把0上面的石子从树上拿走放入口袋；
把每个点上的石子移到其父亲上；
对于每个点，若其石子数≥ 2，则移除该点所有石子（不 放入口袋）。
求对于所有2^{N+1}2N+1种放置石子的方案，最终Sunke口袋中石子数的和为多少，对1000000007取模。
1 ≤ N < 200000，有一部分数据满足1 ≤ N < 2000。
算法标签：启发式DP（首次听说dp可以启发式！nb）
网路上有很多详细清晰的题解（懒惰不想写题解）
以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=2e5+5,p=1e9+7; int n,head[N],ne[N],to[N],rt[N],inv2=p-p/2,cnt; struct node{ int f[3]; node(int a,int b,int c){f[0]=a;f[1]=b;f[2]=c;} };vector<node> q[N]; il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;} il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;} il int mu(int x,int y){if(x+y>=p)return x+y-p;return x+y;} il LL ksm(LL a,int y){LL b=1;while(y){if(y&1)b=b*a%p;a=a*a%p;y>>=1;}return b;} il int merge(int x,int y){ if(q[x].size()<q[y].size())swap(x,y); int xsz=q[x].size(),ysz=q[y].size(); for(int i=0;i<ysz;i++){ int px=xsz-i-1,py=ysz-i-1; int t0,t1,t2; t0=1ll*q[x][px].f[0]*q[y][py].f[0]%p; t1=mu(1ll*q[x][px].f[0]*q[y][py].f[1]%p,1ll*q[x][px].f[1]*q[y][py].f[0]%p); t2=mu(1ll*q[x][px].f[2]*q[y][py].f[2]%p,mu(1ll*q[x][px].f[2]*q[y][py].f[1]%p,1ll*q[x][px].f[2]*q[y][py].f[0]%p)); t2=mu(mu(t2,1ll*q[x][px].f[0]*q[y][py].f[2]%p),mu(1ll*q[x][px].f[1]*q[y][py].f[2]%p,1ll*q[x][px].f[1]*q[y][py].f[1]%p)); q[x][px]=node(t0,t1,t2); } q[y].clear();return x; } il void dfs(int x){ rt[x]=x;int dep=0; if(!head[x]){ q[x].push_back(node(inv2,inv2,0));return; } for(int i=head[x];i;i=ne[i]){ dfs(to[i]); dep=max(dep,(int)min(q[rt[x]].size(),q[rt[to[i]]].size())); rt[x]=merge(rt[x],rt[to[i]]); } int now=rt[x];int s=q[now].size()-1; for(int i=0;i<dep;i++){ q[now][s-i].f[0]=mu(q[now][s-i].f[2],q[now][s-i].f[0]);q[now][s-i].f[2]=0; } q[now].push_back(node(inv2,inv2,0)); } int main() { n=read();for(int i=1;i<=n;i++){int x=read();insert(x,i);} dfs(0);LL ans=0; for(int i=0;i<q[rt[0]].size();i++) ans=mu(ans,q[rt[0]][i].f[1])%p; printf("%lld ",ans*ksm(2,n+1)%p); return 0; }