Codeforces #384 Div2 D. Chloe and pleasant prizes

割と典型な気が。
http://codeforces.com/contest/743/problem/D

問題

N頂点の根付き木があり、各頂点にはスコアが振られている。
ここから、２つの互いに共通部分を持たないsubtreeを選択し、含まれる頂点のスコアの総和を最大化せよ。

解法

木DPで、各頂点vで以下の２値を更新する。
sum(v) := vのsubtree内の頂点のスコアの総和
best(v) := vのsubtree内の頂点のうち、その頂点のsum(v)の最大値

vが子頂点C(v)を2個以上持つ場合、異なる２つの子頂点中のsubtreeを選択すれば、それらは共通部分を持たない。
よってbest(C(v)[1]) + best(C(v)[2]) (ただしC(v)[1],C(v)[2]は子頂点c∈C(v)のうちbest(c)が大きいもの上位２個)が解の候補となる。
あとは各頂点vについて、best(C(v)[1]) + best(C(v)[2])の最大値を求めればよい。

int N;
ll A[202020];
vector<int> E[202020];
ll ma=-1LL<<60;
ll dp[202020];
ll sum[202020];

void dfs(int cur,int pre) {
	sum[cur]=A[cur];
	vector<ll> V;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		sum[cur]+=sum[e];
		V.push_back(dp[e]);
	}
	sort(ALL(V));
	reverse(ALL(V));
	if(V.size()>=2) ma=max(ma,V[0]+V[1]);
	if(V.size()) dp[cur]=max(V[0],sum[cur]);
	else dp[cur]=sum[cur];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1);
	
	if(ma==-1LL<<60) cout<<"Impossible"<<endl;
	else cout<<ma<<endl;
}

まとめ

これはすんなり解けたので「Div2とはいえこれ2000ptは易しすぎない？」と思った。