트리 dp Codeforces Round #168(Div. 2) D 문항 Zero Tree

Zero Tree
A tree is a graph with n vertices and exactly n - 1 edges; this graph should meet the following condition: there exists exactly one shortest (by number of edges) path between any pair of its vertices.
A subtree of a tree T is a tree with both vertices and edges as subsets of vertices and edges of T.
You’re given a tree with n vertices. Consider its vertices numbered with integers from 1 to n. Additionally an integer is written on every vertex of this tree. Initially the integer written on the i-th vertex is equal to vi. In one move you can apply the following operation:
Select the subtree of the given tree that includes the vertex with number 1. Increase (or decrease) by one all the integers which are written on the vertices of that subtree. Calculate the minimum number of moves that is required to make all the integers written on the vertices of the given tree equal to zero.
제목 대의: n개의 결점을 가진 나무에게 각 결점마다 하나의 권한이 있다. 결점 1을 포함하는 하위 나무(1은 기호이지 권한이 아니다)를 선택하고 이 하위 나무의 권한을 빼거나 1을 더하면 최소 조작 횟수를 물어보면 나무의 모든 점의 권한이 0이 된다.
분석을 통해 알 수 있듯이 한 개의 자수의 뿌리 결점에 대해 최소한 그 자노드의 권한값의 최소값의 절대값(자결점의 권한값이 마이너스일 경우)을 더해야 하고 최소한 그 자노드의 권한값의 최대값(자결점의 권한값이 플러스일 경우)을 빼야 한다.
그래서 두 개의 수조를 열 수 있다. decr[i]는 i가 뿌리인 트리에서 빼야 할 값을 표시하고, inc[i]는 i가 뿌리인 트리에서 빼야 할 값을 나타낸다.매번 최대치를 찾으면 된다.
루트 결점을 업데이트하는 작업에 주의하기;
코드:

#include
#define LL long long
#define pa pair
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=100100;
const int M=2000100;
const LL mod=1e9+7;
int head[N],cnt,n; 
LL inc[N],decr[N],a[N];
struct Node{
     
	int to,nex;
}edge[N*2];
void add(int p,int q){
     
	edge[cnt].to=q,edge[cnt].nex=head[p],head[p]=cnt++;
}
void dfs(int p,int ft){
     
	LL mx1=-1,mx2=-1;
	for(int i=head[p];~i;i=edge[i].nex){
     
		int q=edge[i].to;
		if(q!=ft){
     
			dfs(q,p);
			mx1=max(mx1,inc[q]),mx2=max(mx2,decr[q]);
		}
	}
	if(mx1==-1&&mx2==-1){
     
		if(a[p]>=0) decr[p]=a[p];
		else inc[p]=-a[p];
	}
	else{
     
		decr[p]=mx2,inc[p]=mx1; 
		a[p]+=mx1-mx2;
		if(a[p]>=0) decr[p]+=a[p];
		else inc[p]+=-a[p];
	}
}
int main(){
     
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for(int i=1;i<n;i++){
     
		int a,b;scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	dfs(1,-1);
	printf("%lld
",decr[1]+inc[1]);
	return 0;
}