【题目】E - Smuggling Marbles
【题意】给定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=200010,MOD=1000000007; int read(){char c;int s=0,t=1;while(!isdigit(c=getchar()))if(c=='-')t=-1;do{s=s*10+c-'0';}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=0,tot=0,b[maxn]; struct edge{int v,from;}e[maxn*2]; 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=0;i<(int)a[y].size();i++){a[x][a[x].size()-i-1]=a[x][a[x].size()-i-1]+a[y][a[y].size()-i-1];} } int main(){n=read()+1;for(int i=2;i<=n;i++)fa[i]=read()+1,insert(fa[i],i);for(int i=n;i>=1;i--){int mx=0;if(!first[i]){a[b[i]=++tot].push_back((cyc){(MOD+1)/2,(MOD+1)/2,0});}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+1)/2,(MOD+1)/2,0});}for(int j=(int)a[b[i]].size()-1-1;j>=(int)a[b[i]].size()-mx-1;j--)a[b[i]][j].z0+=a[b[i]][j].z2,a[b[i]][j].z2=0;}int ans=0,N=1;for(int i=1;i<=n;i++)N=(N<<1)%MOD;for(int i=0;i<(int)a[b[1]].size();i++)ans=MO(ans+1ll*a[b[1]][i].z1*N%MOD);printf("%d",ans);return 0; }