P6293 [eJOI2017] 经验

wflengxuenong · 2022-11-07 15:01:49 · 个人记录

/*

可以发现，这个划分的过程把树分成了n条链。
如果每个点单独，那么有最小值0，要想取得最大值，要将将递增或递减的分在不同的链里。
设dp[u][0/1]为以u为节点，当前点属于上升链还是递减链。
u由三种可能的情况：
1.u点不属于任何孩子链，每个孩子在单独的链。
2.在某个孩子连接的递减的链上
3.在某个孩子连接的递增链上
*/ 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+9;
int n;
ll w[N],dp[N][2];
vector<int> t[N];
void dfs(int u) {
    ll sm=0;
    for(auto v:t[u]) {
        dfs(v);
        sm+=max(dp[v][0],dp[v][1]);
    }
    dp[u][0]=dp[u][1]=sm;
    //把当前节点放在哪个链上呢？都试试取最优质，扣去这个v链，u在v链上产生新的价值。
    for(auto v:t[u]) {
        if(w[v]<=w[u])//在递减的链上
            dp[u][0]=max(dp[u][0],sm-max(dp[v][0],dp[v][1])+w[u]-w[v]+dp[v][0]);
        if(w[v]>=w[u])//在递增的链上 ，u在
            dp[u][1]=max(dp[u][1],sm-max(dp[v][0],dp[v][1])+w[v]-w[u]+dp[v][1]);
    }
    return ;
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%lld",&w[i]);
    for(int i=1; i<n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);//有向树
        t[x].push_back(y);
    }
    dfs(1);
    printf("%lld\n",max(dp[1][0],dp[1][1]));
    return 0;
}