Parsa's Humongous Tree

问题：树上每个点上的值 $a_v$ 取值范围是 $l_v$ , $r_v$ ，每条边 $(u,v)$ 的价值是 $|a_u-a_v|，求$ a_v$最优的情况下，所有边的总价值的最大值是多少。

直观来想，边的价值是两端点的差的绝对值，也就是端点相差越大越好。可以想到一条路是对每个子树顶点所有可能的取值求DP，但因为 $n \leq 10^5$ ， $a$ 的取值范围很大（ $10^9$ ），而且也没有唯一性等条件，所以这个至少 $\mathcal{O}(n^2)$ ，不可行。

观察有没有可以利用的数学性质，可以想到对于两个点的简单情况，最优值都在极值的情况下取得，就是两个点取 $ll,lr,rl,rr$ 四种情况以一。实际上，这个结论可以推广到更多节点的情况，只有当节点值取左右边界的时候，才有可能是最优的。

那这样我们的状态就好构造了：

\text{dp}[i][j] = \begin{cases} j=0 & i\texttt{子树的最大差值和，当}i\texttt{处选择}l_i\texttt{的时候} \\ j=1 & i\texttt{子树的最大差值和，当}i\texttt{处选择}r_i\texttt{的时候} \\ \end{cases}

状态转移是：

dp[i][0] = \max_{u \in C_i} (dp[u][0] + |l_i-l_u|, dp[u][1] + |l_i-r_u|) \\ dp[i][1] = \max_{u \in C_i} (dp[u][0] + |r_i-l_u|, dp[u][1] + |r_i-r_u|) \\

然后答案是 $\max(dp[0][0], dp[0][1])$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, n;
vector<int> adj[100005];
ll dp[100005][2];   // 0: pick left, 1: pick right
int l[100005], r[100005];
 
void dfs(int s, int e) {
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs(u, s);
        // update dp[s], pick l or r for u
        dp[s][0] += max(abs(l[s]-l[u]) + dp[u][0], abs(l[s]-r[u]) + dp[u][1]);
        dp[s][1] += max(abs(r[s]-l[u]) + dp[u][0], abs(r[s]-r[u]) + dp[u][1]);
    }
}
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            adj[i].clear(), dp[i][0] = dp[i][1] = 0;
        for (int i = 0; i < n; i++)
            scanf("%d %d", &l[i], &r[i]);
        for (int i = 0; i < n-1;i ++) {
            int u,v;
            scanf("%d %d", &u, &v);
            u--,v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(0, -1);
        printf("%lld\n", max(dp[0][0], dp[0][1]));
    }
    return 0;
}