Submission #2704375

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 200003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;
struct aa{
	long long x,y,z;
};
vector<aa>dp[mx];
long long level[mx],p[mx],n,pake[mx],idx,depth[mx];
vector<int>ve,g[mx];
void dfs(int now,int lev){
	level[now]=depth[now]=lev;
	//debug(now);
	ve.pb(now);
	int cnt=0;
	for(int i:g[now]){
		dfs(i,lev+1);
		depth[now]=max(depth[now],depth[i]);
		cnt=1;
	}
	if(cnt==0){
		pake[now]=++idx;
	}
}

bool cmp(int x,int y){
	return level[x]>level[y];
}

bool cmp2(int x,int y){
	return depth[x]<depth[y];
}

const long long ini=500000004;

int main(){
	cin>>n;
	long long pang=1;
	for(int i=0;i<=n;i++)pang=(pang*2)%MOD;
//	debug(pang);
	for(int i=1;i<=n;i++){
		cin>>p[i];
		g[p[i]].pb(i);
	}
	long long jaw=0;
	dfs(0,1);
	for(int i=0;i<=n;i++)sort(ALL(g[i]),cmp2);
	sort(ALL(ve),cmp);
	for(int i:ve){
		if(pake[i]){
			dp[pake[i]].pb({ini,ini,0});
			continue;
		}
		int cnt=0;
		for(int j:g[i]){
			if(cnt==0 && g[i].size()>1){
				pake[i]=pake[j];
				for(auto &k:dp[pake[i]]){
					k.x=(k.x+k.z)%MOD;
					k.z=0;
				}
				cnt++;
				continue;
			}
			else if(cnt==0){
				pake[i]=pake[j];
				break;
			}
			int x=dp[pake[i]].size()-1,y=dp[pake[j]].size()-1;
			assert(x<=y);
			for(;x>=0 && y>=0;x--,y--){
				auto tmp=dp[pake[j]][y];
				auto &now=dp[pake[j]][y];
				auto sem=dp[pake[i]][x];
				//0 -> 0 dan 2
				now.x=(sem.x*((tmp.x+tmp.z)%MOD))%MOD;
				//1 -> 0 dan 1, 1 dan 0
				now.y=(sem.x*tmp.y)%MOD;
				now.y=(now.y+(sem.y*((tmp.x+tmp.z)%MOD))%MOD)%MOD;
				//2 ->1 dan 1, 2 dan 0, 2 dan 1
				now.z=(sem.y*tmp.y)%MOD;
				now.z=(now.z+(sem.z*((tmp.x+tmp.z)%MOD))%MOD)%MOD;
				now.z=(now.z+(sem.z*tmp.y)%MOD)%MOD;
			}
			if(i==0){
				debug(j);
				debug(depth[j]);
			}
			pake[i]=pake[j];
		}
	//	debug(i);
		dp[pake[i]].pb({ini,ini,0});
	}
	for(auto i:dp[pake[0]]){
		long long sem=(i.y*pang)%MOD;
		jaw=(jaw+sem)%MOD;
	}
	cout<<jaw<<endl;
}

Submission Info

Judge Result