codeforces275D - Zero Tree 트리 dp

이 문제는 처음에 풀 때 나무형 dp를 생각한 후에 자신의 비뚤어진 사고방식에 의해 바로 귀착되었다. 당시에 가감을 분리하는 것을 고려하지 못하고 직접 abs가 누적되어 부끄러웠다.
D. Zero Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
Input
The first line of the input contains n (1 ≤ n ≤ 105). Each of the next n - 1 lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi) indicating there's an edge between vertices ai and bi. It's guaranteed that the input graph is a tree.
The last line of the input contains a list of n space-separated integers v1, v2, ..., vn (|vi| ≤ 109).
Output
Print the minimum number of operations needed to solve the task.
Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
Examples
input
Copy

3
1 2
1 3
1 -1 1

output
Copy

3

dp수조 0은 몇 개의 1을 더해야 현재의 수에 도달할 수 있고, 1은 몇 개의 1을 더 줄여야 현재의 수에 도달할 수 있음을 나타낸다.각 노드에 최대 두 명의 아들이 있다. (각 점의 수치 정수는 마이너스를 대표하고 감소를 대표한다) 그리고 현재 노드에 대해 조작을 해서'원래'의 수치를 구한다. 즉, 그가 추가한 값을 뺀 값을 더하면 0보다 작으면 감소한다는 것을 의미한다. 그리고 그에게 마지막으로 1 노드로 돌아가는 것을 보충한다. 나는 인접표로 직접vector를 막지 않고 표기수조를 추가했다.

#include 
#include 
#include 
#include 
#include 
#define MAXN 20
#define INF 0x3f3f3f3f
 
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
vectora[100020];
long long e[200003],dp[200000][2],maxx[200001],minn[200001];
bool ha[2000020];
void dfs(int x)
{
    ha[x]=1;
    dp[x][0]=dp[x][1]=0;
    for(int i=0;i0)
dp[x][0]+=e[x];
else
dp[x][1]-=e[x];
return ;
}
int main()
{
long long n,m;
cin>>n;
for(int i=1;i>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
cin>>e[i];
}
memset(ha,false,sizeof(ha));
dfs(1);
long long ans=dp[1][1]+dp[1][0];
cout<