人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Codeforces Round #530 (Div. 1):A. Sum in the tree

問題

codeforces.com

解法

b_i を「頂点 i を根とする全て部分木に含まれる s の最小値」とおく.このとき,b_i < s_i であるような頂点が存在したらその木は構成不可能なので -1 を出力すればよい.

木が構成出来る場合,木全体を根から(すなわち頂点 1 から)見ていく.「dfs(i, s) := 今頂点 i を見ていて,パスにある頂点の a の和が sum のとき」と DFS を立てて,a_i = b_i - sum とすればよい.これを全ての頂点について処理し a を求めればよい.O(N).

解答

codeforces.com

f:id:babcs2035:20190319065853p:plain