CF1528A Parsa‘s Humongous Tree

CF传送门

题目大意:大小为 n n n的一棵树 i i i号节点有权值范围 [ l i , r i ] [l_i,r_i] [li​,ri​]让你对每个节点赋予一个权值 a i a_i ai​,使得每个节点权值都在规定的范围里并且对于每条边 ( u , v ) (u,v) (u,v), ∑ ∣ a u − a v ∣ \sum{|a_u-a_v|} ∑∣au​−av​∣最大,并求出这个最大值。

一道典型的树形 d p dp dp,和没有上司的舞会差不多

首先根据货仓选址的结论,我们很容易想到,对于每个 v v v, ∑ ∣ a u − a v ∣ \sum{|a_u-a_v|} ∑∣au​−av​∣是关于 a v a_v av​的凸函数,因此只能在 l v l_v lv​或者 r v r_v rv​处取到最优解
猜也能猜到只可能选l或r(
然后我们令 d p 0 / 1 dp_{0/1} dp0/1​代表对于当前这个节点选 l i l_i li​还是 r i r_i ri​
于是我们可以得到转移方程( j j j为 i i i的子节点):
{ d p [ i ] [ 0 ] + = m a x ( d p [ j ] [ 0 ] + a b s ( l [ i ] − l [ j ] ) , d p [ j ] [ 1 ] + a b s ( l [ i ] − r [ j ] ) ) d p [ i ] [ 1 ] + = m a x ( d p [ j ] [ 0 ] + a b s ( r [ i ] − l [ j ] ) , d p [ j ] [ 1 ] + a b s ( r [ i ] − r [ j ] ) ) \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} {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]))​
最终 a n s = m a x ( d p [ 1 ] [ 0 ] , d p [ 1 ] [ 1 ] ) ans=max(dp[1][0],dp[1][1]) ans=max(dp[1][0],dp[1][1])
P S PS PS:多组数据, t o t tot tot记得清零,不然 M L E MLE 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;
}
上一篇:2021.07.16【NOIP提高B组】模拟 图书馆


下一篇:iOS中两个APP之间的跳转和通信