この類の問題、よく一発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; }
まとめ
こういうのいつも微妙にミスするのにね。