1528A - Parsa's Humongous Tree - CodeForces Solution

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e9+7;
vector <int> v[1000001];
ll dp[1000001][2];
ll vis[1000001];
ll l[1000001],r[1000001];
ll n;
void dfs (ll u) 
{
	vis[u]=1;
	for (int i:v[u]) 
    {
		if (vis[i]==0) 
		{
			dfs(i);
			dp[u][0]+=max(dp[i][0]+abs(l[i]-l[u]),dp[i][1]+abs(r[i]-l[u]));
			dp[u][1]+=max(dp[i][0]+abs(l[i]-r[u]),dp[i][1]+abs(r[i]-r[u]));
		}
	}
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t; 
	cin >> t;
	while (t--) 
    {
		cin >> n;
		for (int i=1;i<=n;i++) 
        {
			vis[i]=0;
			v[i].clear();
			cin >> l[i] >> r[i];
			dp[i][0]=0;
			dp[i][1]=0;
		}
		for (int i=1;i<n;i++) 
		{
		    ll x, y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1);
		cout << max(dp[1][0],dp[1][1]) << endl;
	}	
}