题解 | 小O的树上路径

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

int n;
vector<vector<pair<int,long long>>> g;
vector<int> parent_;
vector<long long> downv, bestv;
void dfs1(int u, int p){
    parent_[u]=p;
    long long mx = 0;
    for(auto [v,w]: g[u]) if(v!=p){
        dfs1(v,u);
        mx = max(mx, w + downv[v]);
    }
    downv[u]=mx;
}
void dfs2(int u, int p){
    // 先算子树
    for(auto [v,w]: g[u]) if(v!=p) dfs2(v,u);
    // 收集 gain
    long long top1=0, top2=0; int who=-1;
    for(auto [v,w]: g[u]) if(v!=p){
        long long gval = w + downv[v];
        if(gval > top1){ top2 = top1; top1 = gval; who=v; }
        else if(gval > top2){ top2 = gval; }
    }

    long long res = downv[u]; // 不延伸主路径，只在 u 取一次侧枝
    for(auto [v,w]: g[u]) if(v!=p){
        long long side = (v==who ? top2 : top1);
        res = max(res, w + bestv[v] + side);
    }
    bestv[u]=res;
}

int main(){
    cin>>n;
    g.assign(n+1, {});
    for(int i=0;i<n-1;i++){
        int u,v; long long w; cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    parent_.assign(n+1,0);
    downv.assign(n+1,0);
    bestv.assign(n+1,0);

    dfs1(1,0);
    dfs2(1,0);

    cout << bestv[1] << '\n';
    return 0;
}