yukicoder : No.1221 木 *= 3

こちらは典型かな…。
https://yukicoder.me/problems/no/1221

問題

木を成すグラフが与えられる。
各点パラメータとしてA[i]・B[i]が与えられる。

ここで、いくつか任意の点を削除した状態を考える。
この時、このグラフのスコアは以下のように計算される。

• 消された点vに対し、A[v]が加算される。
• 残された点vに対し、隣接点がd個残っているならB[v]*dが加算される。

任意の削除点の組み合わせに対し、最大スコアを求めよ。

解法

以下の3通りを葉から順にDPで求めて行こう。

• 点vを削除したとき、vのSubTreeのスコアの総和の最大値
• 点vを残したとき、親方向の点を残す場合、vのSubTreeのスコアの総和の最大値
• 点vを残したとき、親方向の点を消す場合、vのSubTreeのスコアの総和の最大値

2つ目と3つ目の計算では、どの子を残すか、という計算が必要となる。
その際は、消すより残すことを選ぶことによるスコア増分が多い順に残すようにしよう。

int N;
ll A[101010],B[101010];
vector<int> E[101010];
ll dp[101010][3]; // 0-both alive 1-par dead 2-self dead

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


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

まとめ

問題名の由来は思い浮かばなかったな…。