东非大裂谷

　

东非大裂谷

题意

给出一棵树

每个点上有权值

你需要把这些树分成若干条链，每条链都必须满足上面的点深度互不相同（也就是说不会存在某个点有两个儿子都在链上），每条链的收益是该链上的最大值减去最小值。问最大的总收益

题解

可以发现，由于收益只跟最大值和最小值有关，所以链的两端一定分别是最大值和最小值

也就是说每条链都一定是从上到下单增或单减的，而且这样的话，我们就可以通过把相邻的差值加起来就得到最大减最小了

我们就可以定义d[i][0/1]表示i为根的子树,i所在的的链单增/单减的最大收益

然后就可以比较正常的树形dp了

转移方程见代码吧，比较简单，主要是第一步的转化比较神仙

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=100005;
struct node{
    int u,v,nxt;
}edge[N*2];
int head[N],mcnt;
void add_edge(int u,int v){
    mcnt++;
    edge[mcnt].u=u;
    edge[mcnt].v=v;
    edge[mcnt].nxt=head[u];
    head[u]=mcnt;
}
int w[N];
ll d[N][2];
int n;
void dp(int u){
    ll sum=0;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        dp(v);
        sum+=max(d[v][0],d[v][1]);
    }
    d[u][0]=d[u][1]=sum;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(w[u]<w[v])
            d[u][0]=max(d[u][0],sum-max(d[v][0],d[v][1])+d[v][0]+w[v]-w[u]);
        else
            d[u][1]=max(d[u][1],sum-max(d[v][0],d[v][1])+d[v][1]+w[u]-w[v]);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
    }
    dp(1);
    printf("%lld\n",max(d[1][0],d[1][1]));
}

相关阅读