CF1083A 树形DP The Fair Nut and the Best Path

题目链接：https://www.luogu.org/problem/CF1083A

题意：有n个城市，每个城市可以加油wi，有n-1条道路，每条道路会耗费汽油ei，找出一条链，使得最后的剩下的汽油数量最多。

分析：可以用树形DP来做，dp[i][0]和dp[i][1]分别代表以i为终点和中间点剩下的汽油的数量，找最大的两个儿子，不断更新。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=3e5+7;
int cnt;//记录边的数目
int nxt[maxn*2],head[maxn],to[maxn*2]; 
ll w[maxn],e[maxn*2];
ll dp[maxn][2];
ll ans=0;
void add(int u,int v,ll c){
    ++cnt;
    to[cnt]=v;
    e[cnt]=c;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dp_rule(int u,int fa){
    ll max1=0,max2=0;
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]==fa) continue;
        int v=to[i];
        dp_rule(v,u);
        if(dp[v][0]-e[i]>=max1){
            max2=max1;
            max1=dp[v][0]-e[i];
        }
        else if(dp[v][0]-e[i]>max2){
            max2=dp[v][0]-e[i];
        }
    }
    dp[u][0]=max1+w[u];
    dp[u][1]=max1+max2+w[u];
    ans=max(ans,max(dp[u][0],dp[u][1]));
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%I64d",&w[i]);
    }
    int u,v;ll c;
    for(int i=1;i<n;i++){
        scanf("%d%d%I64d",&u,&v,&c);
        add(u,v,c);
        add(v,u,c);
    }
    dp_rule(1,0);
    printf("%I64d
",ans);
    return 0;
}