题意描述：有一个编号为1-n的树，每个节点v都有一个区间[lv,rv],这个节点可以取这个范围内的值(记为av)，两个直接相连的节点(u,v)产生的贡献为|au-av|，求整棵树的贡献和的最大值。

设f(x)=|x-a1|+|x-a2|+……+|x-ak|为节点x对答案产生的贡献，其中a1~ak为x的每个相连的节点的取值，显然f(x)max=max(f(lx),f(rx) ).
据此有如下贪心：为了使贡献和最大，每个节点必取最左或最右。

问题转化为：有一个编号为1-n的树，每个节点v的取值必为lv或rv(取值记为av)，两个直接相连的节点(u,v)产生的贡献为|au-av|，求整棵树的贡献和的最大值。

取根节点为1，记f[i][0/1]为第i号节点取li或ri时，它的 子树 的贡献和的最大值，得状态转移方程：
f[x][0]+=max(f[y][0]+abs(v[x][0]-v[y][0]),f[y][1]+abs(v[x][0]-v[y][1]) );
f[x][1]+=max(f[y][0]+abs(v[x][1]-v[y][0]),f[y][1]+abs(v[x][1]-v[y][1]) );
其中li=v[i][0],ri=v[i][1].(i=1,2,……,n)
最后答案为max(f[1][0],f[1][1]).
时间复杂度O(n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll head[200010],nxt[200010],to[200010],tot;
ll f[100010][2];
ll v[100010][2];
ll vis[100010];
ll n;
inline ll maxmy(ll a,ll b)
{
    return a>b?a:b;
}
inline ll absmy(ll a)
{
    return a<0?-a:a;
}
void add(ll x,ll y)
{
    to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
    return ;
}
void del()
{
    tot=0;
    for(ll i=1;i<=n;++i)
    {
        f[i][0]=f[i][1]=head[i]=v[i][0]=v[i][1]=0;
    }
    return ;
}
void dfs(ll x)
{
    ll y;
    for(ll ct=head[x];ct;ct=nxt[ct])
    {
        y=to[ct];
        if(!vis[y])
        {
            vis[y]=1;
            dfs(y);
            vis[y]=0;
            f[x][0]+=maxmy(f[y][0]+absmy(v[x][0]-v[y][0]),f[y][1]+absmy(v[x][0]-v[y][1]) );
            f[x][1]+=maxmy(f[y][0]+absmy(v[x][1]-v[y][0]),f[y][1]+absmy(v[x][1]-v[y][1]) );
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t,x,y;
    cin>>t;
    while(t--)
    {
        del();
        cin>>n;
        for(ll i=1;i<=n;++i)
        {
            cin>>v[i][0]>>v[i][1];
        }
        for(ll i=1;i<n;++i)
        {
            cin>>x>>y;
            add(x,y);add(y,x);
        }
        vis[1]=1;
        dfs(1);
        vis[1]=0;
        cout<<maxmy(f[1][0],f[1][1])<<endl;
    }
    return 0;
}