[CF1083A] The Fair Nut and the Best Path - 树形dp

Description

点有正权，边有负权。在这样的无根树中找到一条权重最大的链并输出权重。
$ 1 \leq n \leq 3 \times 10^5,0 \leq w_i \leq 10^9,1 \leq c_i \leq 10^9 $

Solution

重要结论：如果一条路径正向反向不同时合法，则它一定存在一条子路径比它更优（想到了就很显然）

于是我们就可以当做无向链处理了

设 \(f[i]\) 表示到 \(i\) 结尾的一条直链的最大值

递推 \(f[]\) 时，选取最大儿子即可

更新答案时，选取最大儿子和次大儿子即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

struct edge {
    int q,c;
};

int n,w[N],f[N],v[N],ans;
vector <edge> g[N];

void dfs(int p) {
    v[p]=1;
    int mx=0,sc=0;
    for(edge e:g[p]) {
        int q=e.q, c=e.c;
        if(v[q]) continue;
        dfs(q);
        if(f[q]-c>mx) {
            sc=mx;
            mx=f[q]-c;
        }
        else if(f[q]-c>sc) {
            sc=f[q]-c;
        }
    }
    f[p]=mx+w[p];
    ans=max(ans,mx+sc+w[p]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++) {
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        g[t1].push_back({t2,t3});
        g[t2].push_back({t1,t3});
    }
    dfs(1);
    cout<<ans;
}

[CF1083A] The Fair Nut and the Best Path - 树形dp

原文：https://www.cnblogs.com/mollnn/p/12834350.html