Codeforces Round #722 (Div. 2)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
const int maxx=1e5+10;
pair<long long int,long long int> e[maxx];//建立点的权值的数组
long long int ans[maxx]={0};//标记这个点是不是被读取过
vector<long long int> p[maxx];//记录边
//int sum=0;
/*
struct mp
{
    LL li,ri;
    mp(){}
    mp(LL a,LL b){li=a;ri=b;}
};
vector<LL>p[100005];
int vis[100005];
vector<mp>e;   //另一种的建树方式
LL dp[100005][2];

*/
long long int dp[maxx][2];
long long int solve(long long int v){
    ans[v]=1;
    for(int i=0;i<p[v].size();i++){
        if(ans[p[v][i]]==1){
            continue;
        }
        solve(p[v][i]);
        int k=p[v][i];
        dp[v][0]+=max(dp[k][0]+abs(e[v].first-e[k].first),dp[k][1]+abs(e[v].first-e[k].second));
        dp[v][1]+=max(dp[k][0]+abs(e[v].second-e[k].first),dp[k][1]+abs(e[v].second-e[k].second));
        //不是直等于，是加和，因为这不是链，是树，一个点好多邻接点
    }

    return max(dp[v][0],dp[v][1]);

}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            int l,r;
            scanf("%lld %lld",&e[i].first,&e[i].second);

            dp[i][0]=0;
            dp[i][1]=0;
            p[i].clear();
            ans[i]=0;
        }
        for(int i=1;i<n;i++){
            long long int a,b;
            scanf("%lld %lld",&a,&b);
            p[a].push_back(b);
            p[b].push_back(a);
        }
        int flagi=0;
        
        for(int i=1;i<=n;i++){
            if(p[i].size()==1){
                flagi=i;
                break;
            }
        }


        long long int sum=solve(flagi);
        printf("%lld\n",sum);
    }
}