CF1528A Parsa‘s Humongous Tree

CF传送门

题目大意：大小为$n$的一棵树$i$号节点有权值范围$[l_i,r_i]$让你对每个节点赋予一个权值$a_i$,使得每个节点权值都在规定的范围里并且对于每条边$(u,v)$，$\sum{|a_u-a_v|}$最大,并求出这个最大值。

一道典型的树形$dp$，和没有上司的舞会差不多

首先根据货仓选址的结论，我们很容易想到，对于每个$v$，$\sum{|a_u-a_v|}$是关于$a_v$的凸函数，因此只能在$l_v$或者$r_v$处取到最优解
猜也能猜到只可能选l或r（
然后我们令$dp_{0/1}$代表对于当前这个节点选$l_i$还是$r_i$
于是我们可以得到转移方程($j$为$i$的子节点)：
$\begin{cases}dp[i][0]+=max(dp[j][0]+abs(l[i]-l[j]),dp[j][1]+abs(l[i]-r[j])) \\dp[i][1]+=max(dp[j][0]+abs(r[i]-l[j]),dp[j][1]+abs(r[i]-r[j]))\end{cases}$
最终$ans=max(dp[1][0],dp[1][1])$
$PS$:多组数据，$tot$记得清零，不然$MLE$，被自己傻到
AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;

int l[N],r[N],n,t;
ll dp[N][2];        
int head[N],nex[N],ver[N],tot;
void add(int x,int y){
    ver[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}
void dfs(int x,int fa){
    for(int i=head[x];i;i=nex[i]){
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        dp[x][0]+=max(dp[y][0]+abs(l[y]-l[x]),dp[y][1]+abs(r[y]-l[x]));
        dp[x][1]+=max(dp[y][1]+abs(r[y]-r[x]),dp[y][0]+abs(r[x]-l[y]));
    }
}
int main(){

    scanf("%d",&t);
    while(t--){
        memset(dp,0,sizeof(dp));
        memset(head,0,sizeof(head));
        tot=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)  scanf("%d%d",&l[i],&r[i]);
        for(int i=1;i<n;i++){
            int a,b;
             scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        dfs(1,0);
        printf("%lld\n",max(dp[1][0],dp[1][1]));
    }
    return 0;
}