C. Parsa's Humongous Tree

首先每个顶点的值。如果,证明如下：
假设有个靠近顶点的顶点满足
假设有个靠近顶点的顶点满足
那么当时，将减小到会使得整棵树的美丽值增大
当时，将增大到会使得整棵树的美丽值增大
当时，将变成或会使得整棵树的美丽值不变或增大

定义表示时，的子树的美丽值之和，同理。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int maxn = 1e5 + 7, maxm = 2e5 + 7;
int head[maxn],Next[maxm],to[maxm],tot;
inline void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int l[maxn],r[maxn],f[maxn][2];
void dfs(int x,int fa) {
    for(int i=head[x],y;i;i=Next[i]) {
        if((y=to[i])==fa) continue;
        dfs(y,x);
        f[x][0]+=max(f[y][1]+abs(l[x]-r[y]),f[y][0]+abs(l[x]-l[y]));
        f[x][1]+=max(f[y][1]+abs(r[x]-r[y]),f[y][0]+abs(r[x]-l[y]));
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _,n;
    cin>>_;
    while(_--) {
        cin>>n; tot=0;
        for(int i=1;i<=n;++i) cin>>l[i]>>r[i],f[i][0]=f[i][1]=head[i]=0;
        for(int i=2,x,y;i<=n;++i) {
            cin>>x>>y;
            add(x,y); add(y,x);
        }
        dfs(1,0);
        cout<<max(f[1][0],f[1][1])<<'\n';
    }
    return 0;
}