Submission #3227132

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P 1000000007LL
#define MAXN 200010
struct state {
	ll c0, c1, c2;
	state(){
		c0 = 1, c1 = 1, c2 = 0;
	}

	struct state& operator += (const state &a){
		c2 = (a.c1 + a.c2) *(c1 + c2) + a.c0*c2 + c0*a.c2;
		c1 = a.c1*c0 + a.c0*c1;
		c0 = a.c0*c0;

		c0 %= P;
		c1 %= P;
		c2 %= P;
	}
};

vector<state> ans[MAXN];
int id[MAXN];

int level[MAXN];
int cnt[MAXN];

int p[MAXN];
vector<int> gr[MAXN];

void dfs(int u){
	if(gr[u].size() == 0){
		id[u] = u;
		ans[u].push_back(state());
		return;
	}

	int ma = -1;
	int i_ma = 0;
	for(auto &v : gr[u]){
		level[v] = level[u]+1;
		cnt[level[v]]++;
		dfs(v);
		if((int)ans[id[v]].size() > ma){
			ma = ans[id[v]].size();
			i_ma = v;
		}
	}

	id[u] = id[i_ma];
	int t = ans[id[u]].size();
	for(auto &v : gr[u]){
		if(v == i_ma) continue;
		int t1 = ans[id[v]].size();
		for(int i = 0; i < t1; i++){
			ans[id[u]][t-1- i ] += ans[id[v]][t1-1 - i];
		}
	}
	for(int i = 0; i < ma; i++){
		ans[id[u]][t - 1 - i].c0 += ans[id[u]][t - 1 - i].c2;
		if(ans[id[u]][t - 1 - i].c0 >= P) ans[id[u]][t - 1 - i].c0 -= P;
		ans[id[u]][t - 1 - i].c2 = 0;
	}

	//cout << u << "\n";

	ans[id[u]].push_back(state());
	//for(auto &x : ans[id[u]]) cout << "(" << x.c0 << ", " << x.c1 << ", " << x.c2 << ") ";
	//cout << "\n";
}

ll pot2[MAXN];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	pot2[0] = 1;
	for(int i = 1; i < MAXN; i++){
		pot2[i] = pot2[i-1] << 1;
		if(pot2[i] >= P ) pot2[i] -= P;
	}
	int N;
	cin >> N;

	p[0] = -1;
	cnt[0] = 1;
	
	for(int i = 1; i <= N; i++) {
		cin >> p[i];
		gr[p[i]].push_back(i);
	}

	dfs(0);
	ll sol = 0;
	int t = ans[id[0]].size();
	for(int l = 0; l < t; l++){
		sol += ans[id[0]][t-1-l].c1 * pot2[N + 1 - cnt[l]];
		sol %= P;
	}
	cout << sol << "\n";


	return 0;
}

Submission Info

Judge Result