勉強になりました。
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; }
まとめ
コードはとてもシンプル。