Submission #1985956

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<list>
#include<algorithm>
using namespace std;
#define si scanf
#define so printf
#define N 200100
#define M 
#define INF  
#define mod %P
#define nxt t[j]
template<typename TP>inline bool rd(TP& r)
{
	r=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9')
	{
		if(tmp==EOF)
			return 0;
		tmp=getchar();
	}
	while('0'<=tmp&&tmp<='9')
	{
		r=(r<<3)+(r<<1)+tmp-'0';
		tmp=getchar();
	}
	return 1;
	
} 
long long P=1000000007,ans;
int n;
int h[N],fa[N][30],x[N*2],t[N*2],tot=1;
void ade(int u,int v)
{
	++tot;
	x[tot]=h[u];
	h[u]=tot;
	t[tot]=v;
}
/*int hd[N],xd[N*2],td[N*2],lst[N];
void ins(int u,int v)
{
	++tot;
	xd[lst]=tot;
	td[tot]=v;
}*/
void fathers()
{
	for(int i=1;(1<<(i-1))<=n;++i)
	for(int j=1;j<=n;++j)
		fa[j][i]=fa[fa[j][i-1]][i-1];
}
long long f[N][2];
long long pl[N],pr[N];
int sons[N];
long long power(long long ori,long long t)
{
	long long re=1;
	while(t)
	{
		if(t&1)
			re=re*ori mod;
		ori=ori*ori mod;
		t>>=1;
	}
	return re;
}
int tr[N*2];
void add(int po,int pl)
{
	for(;po<=n+100;po+=(-po)&po)
		tr[po]+=pl;
}
int ask(int po)
{
	int re=0;
	for(;po;po-=(-po)&po)
		re+=tr[po];
	return re;
}
int l[N],r[N],cnt[N];
int d[N];
list<int> ln[N];
void init(int now)
{
	//ins(d[now],now);
	ln[d[now]].push_back(now);
	l[now]=++tot;
	for(int j=h[now];j;j=x[j])
		d[nxt]=d[now]+1,init(nxt); 
	r[now]=tot;
}
long long g[N];
queue<int> Q;
int getlca(int now)
{
	int u=now;
	for(int i=20;i>=0;--i)
		if(ask(r[fa[u][i]])-ask(l[fa[u][i]]-1)<=0)
			u=fa[u][i];
	u=fa[u][0];
	return u;
}
bool vis[N];
struct sta
{
	int po,dp;
	sta(int pos=0,int dep=0)
	{
		po=pos,dp=dep;
	}
	friend bool operator < (sta a,sta b)
	{
		return a.dp<b.dp;
	}
};
priority_queue<sta> q;
void work(int dp)
{
	int now;
	add(l[0],1);
	while(!q.empty())	q.pop();
	list<int>::iterator it;
	for(it=ln[dp].begin();it!=ln[dp].end();it++)
	{
		add(l[*it],1);
		f[*it][1]=1;
		cnt[*it]=1;
		q.push(sta(*it,d[*it]));
	}
	while(!q.empty())
	{
		now=q.top().po;
		q.pop();
		f[now][0]=(power(2,cnt[now])-f[now][1]+P)mod;
		add(l[now],-(ask(l[now])-ask(l[now]-1)));
		
		//更新lca 
		int lca=getlca(now);
		if(lca!=now)
		{
			f[lca][1]=(f[lca][1]*f[now][0]mod+g[lca]*f[now][1]mod)mod;
			g[lca]=g[lca]*f[now][0]mod;
			cnt[lca]+=cnt[now];
			add(l[lca],1);
			if(!vis[lca])
				q.push(sta(lca,d[lca])),vis[lca]=1;
		}
		
		//清空自己 
		g[now]=1;
		vis[now]=0;
		if(now)
		{
			f[now][0]=0,f[now][1]=0;
			cnt[now]=0;
		}
	}
	tot=0;
	ans=(ans+f[0][1]*power(2,n+1-cnt[0])mod)mod;
	f[0][0]=0,f[0][1]=0;
	cnt[0]=0;
}

int main()
{
	rd(n);
	for(int i=1;i<=n;++i)
	{
		rd(fa[i][0]);
		ade(fa[i][0],i);
	}
	for(int i=0;i<=n;++i)
		g[i]=1;
	fathers();
	tot=0;
	init(0);
	for(int i=0;i<=n;++i)
		if(!ln[i].empty())
			work(i);
		else
			break;
	so("%lld\n",ans);
	return 0;
} 

Submission Info

Judge Result