Codeforces Round #168 (Div. 1) B. Zero Tree

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pb push_back
 8 #define pi pair<int,int>
 9 #define fi first
10 #define sc second
11 
12 int n;
13 vector<int>E[maxn];
14 ll a[maxn];
15 ll dp[maxn][2];
16 
17 void dfs(int u,int fa)
18 {
19 
20     for(auto &v:E[u])
21     {
22         if(v==fa) continue;
23         dfs(v,u);
24         dp[u][0]=max(dp[u][0],dp[v][0]);
25         dp[u][1]=max(dp[u][1],dp[v][1]);
26     }
27     a[u]+=dp[u][0]-dp[u][1];
28     if(a[u]>0) dp[u][1]+=a[u];
29     else dp[u][0]+=abs(a[u]);
30 }
31 
32 int main()
33 {
34     ios::sync_with_stdio(0);
35     cin.tie(0);
36     cin>>n;
37     for(int i=1;i<n;i++)
38     {
39         int x,y;
40         cin>>x>>y;
41         E[x].pb(y);
42         E[y].pb(x);
43     }
44     for(int i=1;i<=n;i++) cin>>a[i];
45     dfs(1,0);
46     cout<<dp[1][0]+dp[1][1]<<‘\n‘;
47 
48 
49 
50 
51 
52 }