题目大意
(Sunke)有一棵N + 1个点的树，其中0为根，每个点上有0或1个石子，(Sunke)会不停的进行如下操作直至整棵树没有石子：
把0上面的石子从树上拿走放入口袋；
把每个点上的石子移到其父亲上；
对于每个点，若其石子数(gt1)，则移除该点所有石子（不 放入口袋）。
求对于所有(2^{N+1})种放置石子的方案，最终(Sunke)口袋中石子数的和为多少，对1000000007取模。
(1le N<200000)，有一部分数据满足(1le N <2000)。
题解
显然深度不同的每一层之间不会互相影响,于是我们可以分开算答案
设(dp[u][0/1])表示(u)有0/1个石子的方案数
[设T= prodlimits_{vin son(u)} dp[v][0]\dp[u][1]=sumlimits_{vin son(u)}frac{T}{dp[v][0]}dp[v][1]\dp[u][0]=prodlimits_{vin son(u)} (dp[v][0]+dp[v][1])-dp[u][1]\
]
其实就是容斥,用全部的方案减去1的方案
这个东西就可以用长链剖分的套路去优化
我们每次优先合并长链的深度相同的(dp)值
最后的复杂度是(O(n))的.
听说建颗虚树也可以做
但我不会.
/*
@Date : 2019-10-05 13:07:36
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
#define RG register
#define gi geti<int>()
#define gl geti<ll>()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>
IL T geti()
{
RG T xi=0;
RG char ch=gc;
bool f=0;
while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10);
putchar(k%10+'0');
if(ch)putchar(ch);
}
typedef pair<ll,ll> pll;
int n;
const int N=2e5+7,P=1e9+7;
ll ksm(ll a,int b,ll c=1)
{
for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P;
return c;
}
ll inv(ll x){return ksm(x,P-2);}
struct edge{int v,nxt;}e[N];
int head[N],cnt;
inline void add(int u,int v){e[++cnt]=(edge){v,head[u]},head[u]=cnt;}
inline void init(){memset(head,cnt=-1,sizeof head);}
vector<pll>dp[N];
ll All[N],T[N],One[N];
int id[N],num,d[N];
#define mp make_pair
#define fi first
#define se second
#define For_tree(x) for(int _i=head[x],v=e[_i].v;~_i;_i=e[_i].nxt,v=e[_i].v)
inline void dfs(int x)
{
int hson=n+1,tot=0;
For_tree(x)
{
dfs(v);++tot;
if(d[v]>d[hson])hson=v;
}
if(hson!=n+1)id[x]=id[hson],d[x]=d[hson]+1;
else id[x]=++num;
dp[id[x]].push_back(mp(1,1));
if(tot==1)return;
for(int i=0;i<d[x];++i)All[i]=1,T[i]=1,One[i]=0;
int dep;
For_tree(x)
for(int i=0;i<=d[v];++i)
{
dep=d[hson]-d[v]+i;
pll t=dp[id[v]][i];
(All[dep]*=(t.fi+t.se))%=P,(T[dep]*=t.fi)%=P;
}
For_tree(x)
for(int i=0;i<=d[v];++i)
{
dep=d[hson]-d[v]+i;
pll t=dp[id[v]][i];
(One[dep]+=T[dep]*inv(t.fi)%P*t.se%P)%=P;
}
for(int i=0;i<d[x];++i)
{
pll &t=dp[id[x]][i];
t.fi=(All[i]-One[i]+P)%P,t.se=One[i];
}
}
int dep[N],tot[N],fa[N];
int main(void)
{
n=gi;init();
for(int i=1;i<=n;++i)fa[i]=gi,add(fa[i],i),dep[i]=dep[fa[i]]+1,++tot[dep[i]];
d[n+1]=-1,++tot[0];
dfs(0);
ll ans=0;
for(int i=0;i<=d[0];++i){
pll t=dp[id[0]][i];
(ans+=t.se*ksm(2,n+1-tot[d[0]-i])%P)%=P;
}
pi(ans);
return 0;
}