CSAcademy Beta Round #8 : E. Max Score Tree

この類の問題、よく一発AC出来たな…。
https://csacademy.com/contest/beta-round-8/#task/max-score-tree

問題

N頂点からなる木が与えられる。
この木の連結した部分グラフを考える。
そのグラフのスコアは、各頂点vにおける次数をf(v)としたとき、入力で与えられる配列Sに対しS[f(v)]の総和となる。
最適な部分グラフを選んだ場合、スコアの最大値を求めよ。

解法

木DPで、各頂点を部分グラフの根とした場合のsubtreeの部分グラフのスコアの最大値と、根としない場合(親と連結する場合)のsubtreeの部分グラフのスコアの最大値を求めよう。
今処理している頂点vの各子頂点cに対し、親と連結する場合のsubtreeの部分グラフのスコア最大値をA(c)とする。
まずA(c)を降順に並べよう。

vを根とする場合、子のうちp個を選ぶとすると、S[p]+(A(c)の上位p個の総和)が求めるスコアになるので、その最大値を解の候補とする。
vを根とすしない場合、子のうちp個を選ぶとすると、S[p+1]+(A(c)の上位p個の総和)が求めるスコアになるので、その最大値を親に伝える。

int N;
ll S[101010];
vector<int> E[101010];
ll dp[101010];
ll ma;

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

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

まとめ

こういうのいつも微妙にミスするのにね。