VK Cup 2015 Round 2 : B. Work Group

VK Cup Round2 online mirrorに参加。
Eを落としてしまったため、多少のHackで追いつかずレート減。
http://codeforces.com/contest/533

問題

1～N番のN人の社員がいる。
1番の社員以外は、それより小さい番号のP[i]が上司である。
各社員の能力はA[i]である。

このN人から何人かを選んでチームを作り、その能力の総和を最大化したい。
ただし、ある人がチームに入るには、その部下(及び部下の部下を再帰的に含む)が偶数人チームに入っていなければならない。

条件を満たす人の選び方のうち、能力の総和の最大値を求めよ。

解法

上司・部下の関係を根付き木と見なし、木DPで解けばよい。
各頂点において、その頂点以下の人を偶数人または奇数人選んだ時の能力の総和を求めていく。
頂点の子頂点以下で偶数人選んでいる場合、その頂点自体もチームに参加することができる。

int N;
vector<int> E[202000];
int P[202000];
ll A[202000];
ll T[2][202000];
ll ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i]>>A[i];
	for(i=1;i<N;i++) E[P[i]-1].push_back(i);
	
	for(i=N-1;i>=0;i--) {
		T[1][i]=-1LL<<60;
		FORR(r,E[i]) {
			ll p0=T[0][i],p1=T[1][i];
			T[0][i]=max(p0+T[0][r],p1+T[1][r]);
			T[1][i]=max(p1+T[0][r],p0+T[1][r]);
		}
		T[1][i]=max(T[1][i],T[0][i]+A[i]);
	}
	cout<<max(T[0][0],T[1][0])<<endl;
}

まとめ

ややこしいけど典型木DPではある。