yukicoder : No.1174 盆栽の剪定

勉強になりました。
https://yukicoder.me/problems/no/1174

問題

二分木を成す根付き木が与えられる。
各頂点には重さW[v]が設定されている。

各頂点の価値は、左の子頂点のSubTreeの重みの総和をL、右の子頂点のSubTreeの重みの総和をRとすると|R-L|となる。
また、木の価値は、各頂点の価値の総和となる。

ここで、いくつかの辺を切断することができるとする。
その際、根頂点を含む連結成分の価値の最大値を求めよ。

解法

絶対値を扱うのは面倒なので、重さの差を取るときはR-LとL-R両方取ると考えてしまえばよい。
各頂点の重さが何倍分だけ解に計上されるか、その係数を考えてみよう。
ある頂点がk倍分計上されるとき、両子頂点は(k+1)倍か(k-1)倍形状される。

よって、頂点vがk倍分計上されるときのvのSubTreeの価値の総和をdp(v,k)とすると
dp(v,k) = max(dp(2*v,k+1)+dp(2*v+1,k-1), dp(2*v,k-1)+dp(2*v+1,k+1),dp(2*v,k+1),dp(2*v+1,k+1)) + k * W[v]
となる。
kの絶対値は高々頂点の高さ程度まで考えればよい。

int N;
ll A[202020];
ll dp[202020][40];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	for(i=N;i>=1;i--) {
		for(j=-18;j<=18;j++) {
			dp[i][j+20]=max({dp[2*i][j+20+1]+dp[2*i+1][j+20-1],dp[2*i][j+20-1]+dp[2*i+1][j+20+1],dp[2*i][j+20+1],dp[2*i+1][j+20+1]})+j*A[i];
		}
	}
	cout<<dp[1][20]<<endl;
}

まとめ

コードはとてもシンプル。