http://codeforces.com/contest/815/problem/C 解法 最適解は以下のような形である（入力が木になっていることに注意）。ここまで分かると dp[頂点][使用した頂点数][根と繋がっているかどうか] という DP ができることが分かる。しかしこれは O(n^3) ではな…

http://codeforces.com/contest/815/problem/B 解法 和の線形性（重ね合わせの原理）を用いて計算するとうまくいく。i 番目の要素以外を 0 として、i 番目の要素が与える影響を調べてみることにする。動的計画法により結果を得ることができるが、それでは O(…