Codeforces #168 Div1. B. Zero Tree

さてB。だんだん難しくなってきた。
http://codeforces.com/contest/274/problem/B

問題

木構造が与えられ、各点に整数値が与えられている。
ここで、木の起点を含んだ部分木を選択し、部分木中のすべての点に１足すか１引くことをコスト１で行える。
全ての点の数値を０にするのにかかるコストを答える。

解法

ある葉の数Vを０にするためには、起点から葉までの各点をコストVかけて-Vを足してやらないといけない。
よって、DFSで各点について以下の処理を行い、足す数Pと引く数Qのペア(P,Q)を返す。

• 各子に対して、(P,Q)それぞれの最大値を求める。それぞれの最大値を(A,B)とする。
• 今の点の値にB-Aを足した値をVとする。最終的な値Vが正なら、その分余分に引き算しないといけないので(P,Q+V)を返す。Vが負なら、余分に足し算しないといけないので(P-V,Q)を返す。

起点においてDFSの結果が(P,Q)の場合、P+Qが回答。

//-------------------------------------------------------
int N;
vector<int> E[100001];
vector<ll> V;

pair<ll,ll> dfs(int cur,int pre) {
	ll l=0,h=0,tv;
	int i;
	
	FOR(i,E[cur].size()) {
		if(E[cur][i]==pre) continue;
		pair<ll,ll> tt=dfs(E[cur][i],cur);
		l = max(l,tt.first);
		h = max(h,tt.second);
	}
	
	tv = V[cur]+h-l;
	if(tv>=0) return make_pair(l+tv,h);
	return make_pair(l,h-tv);
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	FOR(i,N-1) {
		j=GETi()-1;
		l=GETi()-1;
		E[j].push_back(l);
		E[l].push_back(j);
	}
	FOR(i,N) V.push_back((ll)GETi());
	
	pair<ll,ll> tval=dfs(0,-1);
	cout << tval.first+tval.second << endl;
	
	return;
}

まとめ

ややこしいけど何とか解けて良かった。
Codeforceはこういう木やグラフを操作して特定の状態に持っていく問題が好きなイメージ。