fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 +5;
  4. long long n, l[MaxN], r[MaxN], dp[MaxN][2];
  5. vector <long long> a[MaxN];
  6.  
  7. void dfs(long long u, long long par)
  8. {
  9.    for (long long v : a[u])
  10.    {
  11.        if(v!=par)
  12.        {
  13.            dfs(v,u);
  14.            dp[u][0] += max(dp[v][0] + abs(l[v]-l[u]) ,dp[v][1] + abs(r[v]-l[u]));
  15.            dp[u][1] += max(dp[v][0] + abs(l[v]-r[u]) ,dp[v][1] + abs(r[v]-r[u]));
  16.  
  17.        }
  18.    }
  19. }
  20.  
  21. void input()
  22. {
  23.     cin >> n ;
  24.     for (long long i=1; i<=n; i++)
  25.     {
  26.         cin >> l[i] >> r[i];
  27.     }
  28.     for (long long i=1; i<n; i++)
  29.     {
  30.         long long u,v;
  31.         cin >> u >> v;
  32.  
  33.         a[u].push_back(v);
  34.         a[v].push_back(u);
  35.     }
  36. }
  37.  
  38. void solve()
  39. {
  40.     memset(dp,0,sizeof(dp));
  41.     dfs(1,-1);
  42.  
  43.  
  44.     cout << max(dp[1][1],dp[1][0]);
  45. }
  46.  
  47. int main()
  48. {
  49.     ios_base::sync_with_stdio(0);
  50.     cin.tie(0);
  51.  
  52.     input();
  53.     solve();
  54. }
  55.  
Success #stdin #stdout 0.01s 7360KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QhJ5nA
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!