fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef vector<int> vi;
  7. typedef vector<ld> vld;
  8. typedef vector<ll> vll;
  9. typedef vector<pair<ll, ll>> vp;
  10. typedef pair<int, int> pii;
  11. typedef pair<ll, ll> pll;
  12. #define fr first
  13. #define sc second
  14. #define all(a) a.begin(),a.end()
  15.  
  16.  
  17. void Hendi() {
  18.     ios_base::sync_with_stdio(0);
  19.     cin.tie(0);
  20.     cout.tie(0);
  21. #ifndef ONLINE_JUDGE
  22.     freopen("input.txt", "r", stdin);
  23.     freopen("output.txt", "w", stdout);
  24.     freopen("error.txt", "w", stderr);
  25. #endif
  26. }
  27.  
  28. const ll INF = 1e9;
  29. const ll MOD = 1e9 + 7;
  30. const double EPS = 1e-7;
  31. const int N = 1e5 + 5;
  32. const int N1 = 1e5 + 5;
  33. int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  35. char di[] = {'R', 'L', 'D', 'U'};
  36.  
  37. ll mul(ll a, ll b) {
  38.     return ((a % MOD) * (b % MOD)) % MOD;
  39. }
  40.  
  41. ll sub(ll a, ll b) {
  42.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  43. }
  44.  
  45. ll MOD_add(ll a, ll b) {
  46.     return ((a % MOD) + (b % MOD)) % MOD;
  47. }
  48.  
  49. ll n, dp[N][2], v[N][2];
  50. vi adj[N];
  51.  
  52. ll DFS(int u, int p, int type){
  53.     ll &ret = dp[u][type];
  54.     if(~ret) return ret;
  55.     ret = 0;
  56.     for (int i = 0; i < 2; ++i) {
  57.         ll sum = 0;
  58.         for(auto &ch: adj[u]){
  59.             if(ch != p){
  60.                 sum += DFS(ch,u,i);
  61.             }
  62.         }
  63.         if(p) sum += abs(v[p][type] - v[u][i]);
  64.         ret = max(ret,sum);
  65.     }
  66.     return ret;
  67. }
  68.  
  69.  
  70. void solve() {
  71.     cin >> n;
  72.     for (int i = 0; i <= n; ++i) {
  73.         for (int j = 0; j < 2; ++j) {
  74.             dp[i][j] = -1;
  75.         }
  76.     }
  77.     for (int i = 1; i <= n; ++i) {
  78.         cin>> v[i][0] >> v[i][1];
  79.     }
  80.     int x , y;
  81.     for (int i = 0; i < n - 1; ++i) {
  82.         cin>> x >> y;
  83.         adj[x].push_back(y);
  84.         adj[y].push_back(x);
  85.     }
  86.     cout<< DFS(1,0,0) << endl;
  87.     for (int i = 0; i <= n; ++i) {
  88.         adj[i].clear();
  89.     }
  90. }
  91.  
  92.  
  93. int main() {
  94.     Hendi();
  95.     int T = 1;
  96.     cin >> T;
  97.     while (T--) {
  98.         solve();
  99.     }
  100. }
Success #stdin #stdout 0.01s 8956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WwCBXs
language:
C++ (gcc 8.3)
created:
5 hours 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!