Codeforces 274B (168B) Zero Tree

問題

n頂点からなる無向木が与えられる。
頂点iには数字v[i]が書かれている。

この木に対して次の操作を好きなだけ行うことができる。

• 頂点1を含む部分木を選び、その頂点全ての数字を+1する
• 頂点1を含む部分木を選び、その頂点全ての数字を-1する

全ての頂点に書かれた数字を0にするのに必要な操作の回数の最小値を求めよ。

制約条件

n≦100000

v[i]

≦10^9

方針

ノードi以下の部分木を0にするのに必要な+の回数をa[i],
必要な+の回数をb[i]とする。

すると、iの子孫の頂点を0にするときに、
最低でもiを、子孫に必要な+の数の最大値回だけ+を、
子孫に必要な+の数の最大値回だけ-をする必要がある。

その操作を行った後で、まだiのノードの数字に過不足があるなら、
その回数だけiに更に操作を行う必要がある。

これを再帰すればよい。

ソースコード

int n;
ll v[100000];
vector<vi> e;

pi rec(int c, int p){
	pi res = mp(0, 0);
	rep(i, e[c].size()) if(e[c][i] != p){
		pi tmp = rec(e[c][i], c);
		res.first = max(res.first, tmp.first);
		res.second = max(res.second, tmp.second);
	}
	ll a = v[c] + res.first - res.second;
	if(a < 0) res.first += -a;
	else res.second += a;
	return res;
}
int main(){
	cin >> n;
	e.resize(n);
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		e[--a].pb(--b);
		e[b].pb(a);
	}
	rep(i, n) cin >> v[i];
	pi res = rec(0, 0);
	cout << res.first + res.second << endl;
	return 0;
}