ARC086

https://arc086.contest.atcoder.jp/

C
ノーコメント

D
符号を全部揃えれば簡単です。

E（部分点)
木dpしただけ。満点解法はマージテクらしいです。

int N;
int P[MAX_N];
vector<int> G[MAX_N];
int dep[MAX_N];

ll dp[2010][2010][2];

void loop(int v, int d) {
	dep[d]++;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		loop(n, d + 1);
	}
	rep(k, 0, N) {
		ll mul = 1, smul = 1;
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			MUL(mul, dp[k][n][0]);
			MUL(smul, (dp[k][n][0] + dp[k][n][1]) % mod);
		}
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			ADD(dp[k + 1][v][1], mul * dp[k][n][1] % mod * invf(dp[k][n][0]) % mod);
		}
		dp[k + 1][v][0] = (smul - dp[k + 1][v][1] + mod) % mod;
	}
	dp[0][v][0] = dp[0][v][1] = 1;
}

void solve() {
	cin >> N; N++;
	// init(N + 10);
	P[0] = -1;
	rep(i, 0, N - 1) {
		cin >> P[i + 1];
		G[P[i + 1]].pb(i + 1);
	}
	loop(0, 0);
	ll ans = 0;
	rep(i, 0, N + 1) {
		ADD(ans, dp[i][0][1] * mod_pow(2, N - dep[i]) % mod);
	}
	cout << ans << "\n";
}

E(満点)
マージテクします。dp列をいちいちすべて更新しなくていいことに気づくことが重要です。
ビー玉が2つ以上の時の処理に意外に手間取りました。

計算量ですが、高さdにある隣り合う2頂点u,vはlca(u,v)で1回更新されます。
よって高さdにある頂点数をavとするとav-1回の更新で済むので、各高さについて考えればO(N)となります。

int N;
vector<int> G[MAX_N];
deque<ll> S[MAX_N][3];
int dep[MAX_N];

void loop(int v, int d) {
	dep[d]++;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		loop(n, d + 1);
		int mv = sz(S[v][0]), mn = sz(S[n][0]);
		if(mv < mn) {
			rep(k, 0, 3) swap(S[v][k], S[n][k]);
			swap(mv, mn);
		}

		vector<vl> cnt(3, vl(mn, 0));
		vector<ll> vvec(3, 0), nvec(3, 0);

		rep(i, 0, mn) {
			rep(k, 0, 3) {
				if(S[v][k].empty()) vvec[k] = 0;
				else { 
					vvec[k] = S[v][k].front(); S[v][k].pop_front(); 
				}
			}
			rep(k, 0, 3) {
				if(S[n][k].empty()) nvec[k] = 0;
				else { 
					nvec[k] = S[n][k].front(); S[n][k].pop_front(); 
				}
			}
			rep(j, 0, 3) {
				rep(k, 0, 3) {
					ADD(cnt[min(j + k, 2)][i], vvec[j] * nvec[k] % mod);
				}
			}
		}
		rer(i, mn, 0) {
			rep(k, 0, 3) S[v][k].push_front(cnt[k][i]);
		}
	}
	vector<ll> zero, one;  
	for(int i = 0; ; i++) {
		if(S[v][2].empty()) break;
		ll v0 = S[v][0].front(); S[v][0].pop_front();
		ll v1 = S[v][1].front(); S[v][1].pop_front();
		ll v2 = S[v][2].front(); S[v][2].pop_front();
		zero.pb((v0 + v2) % mod);
		one.pb(v1);
	}
	rer(i, sz(zero), 0) {
		S[v][0].push_front(zero[i]);
		S[v][1].push_front(one[i]);
	}
	S[v][0].push_front(1);
	S[v][1].push_front(1);
	S[v][2].clear();
}

void solve() {
	cin >> N; N++;
	rep(i, 0, N - 1) {
		int p; cin >> p;
		G[p].pb(i + 1);
	}
	loop(0, 0);
	ll ans = 0;
	int cnt = 0;
	while(!S[0][1].empty()) {
		ll x = S[0][1].front();
		S[0][1].pop_front();
		ADD(ans, x * mod_pow(2, N - dep[cnt]) % mod);
		cnt++;
	}
	cout << ans << "\n";
}

F
コンテスト中誰も通してないしやばそう。