バチャでこの問題を自力ACしました。
全完気持ち〜〜 の反面、得意分野の問題に時間をかけすぎてしまい、反省です。
問題概要
頂点の木があり、各頂点には-1か1が割り当てられています。各頂点について、自身を含む部分木のうち、部分木の頂点に書かれている数字の総和が最大になるものを選び、その総和を答えなさい。
簡単な 
解法
各頂点 について
を根とした木を考える。頂点
について、
:= 頂点
以下の部分木における総和の最大値
と定義します。これを DFS で全ての子供について を足し上げていくと、できます。
解法
が大きいので、上の解法では TLE してしまいます。上の木DPでは、毎回根を変えてDFSをしていたので時間がかかりすぎてしまいました。
実はこの問題は、最初に一度適当な頂点から上のDFSをすると、親の答えがわかっているとき、自身のDP値から自身を根とした木を定数時間で再構築できます。いわゆる全方位木DPというやつです。一度目の dp 値を用いて、最初の根方向の部分木の dp 値は (node.par->dp - node.dp) として計算できます。葉方向の部分木の dp 値は最初のDFSで求められているので、これにより で全ての頂点について dp 値を求めることができました。
