写在前面的

这是我不想做第二次的题目。

分析

我们什么都不说了，直接定义状态 表示 节点是否作为蓝线的中点的最优解。那么我们通过分析，一条蓝边一定是 的路径。所以先考虑 的暴力树形 。 和 ，然后 就写好了。

#include<bits/stdc++.h>
int read() {int x;scanf("%d",&x);return x;}
using namespace std;
const int N = 12010,inf = 0x3f3f3f3f;
#define pii pair<int,int>
vector<pii> G[N];
int n,f[N][2];
void dfs(int x,int fa) {
    f[x][0] = 0;int tot = 0;
    for(auto e : G[x]) {
        int y = e.first,w = e.second;
        if(y == fa) continue;
        dfs(y,x);tot++;
        f[x][0] += max(f[y][0],f[y][1] + w);
    }
    if(!tot) f[x][1] = -inf;
    if(!tot) return;
    f[x][1] = -inf;
    for(auto e : G[x]) {
        int y = e.first,w = e.second;
        if(y == fa) continue;
        f[x][1] = max(f[x][1],f[y][0] + w - max(f[y][0],f[y][1] + w));
    }
    f[x][1] += f[x][0];
} 
int main() {
    n = read();
    for(int a,b,c,i=1;i<n;i++) {
        a = read();b = read();c=read();
        G[a].push_back(pii(b,c));
        G[b].push_back(pii(a,c));
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) dfs(i,0),ans = max(ans,f[i][0]);
    cout << ans << endl;
}

现在我们考虑如何换根。这里的式子无比恶心，我这里直接放图片吧。 其中 表示这个节点为根的答案。 表示除开这个节点子树的答案。

#include<bits/stdc++.h>
int read() {int x;scanf("%d",&x);return x;}
using namespace std;
const int N = 210000,inf = 0x3f3f3f3f;
#define pii pair<int,int>
vector<pii> G[N];
int n,f[N][2],son1[N],son2[N],mx1[N],mx2[N];
int g[N][2],k[N][2],val[N];
void dfs(int x,int fa) {
    f[x][0] = 0;f[x][1] = -inf;
    mx1[x] = mx2[x] = -inf;son1[x] = son2[x] = 0;
    for(auto e : G[x]) {
        int y = e.first,w = e.second;
        if(y == fa) continue;
        val[y] = w;
        dfs(y,x);
        f[x][0] += max(f[y][0],f[y][1] + w);
    }
    for(auto e : G[x]) {
        int y = e.first,w = e.second;
        if(y == fa) continue;
        int val = f[y][0] + w - max(f[y][0],f[y][1] + w);
        if(val > mx1[x]) {swap(son1[x],son2[x]);swap(mx1[x],mx2[x]);mx1[x]=val;son1[x]=y;}
        else if(val > mx2[x]) {son2[x]=y;mx2[x]=val;}
    }
    f[x][1] = f[x][0] + mx1[x];
} 
void solve(int x,int fa) {
    for(auto e : G[x]) {
        int y = e.first,w = e.second;
        if(y == fa) continue;
        if(son1[x] == y) {swap(son1[x],son2[x]);swap(mx1[x],mx2[x]);}
        k[x][0] = g[x][0] - max(f[y][0],f[y][1] + w);
        k[x][1] = k[x][0] + mx1[x];
        if(fa) {k[x][1] = max(k[x][1],k[x][0] + k[fa][0] + val[x] - max(k[fa][0],k[fa][1]+val[x]));}
        g[y][0] = f[y][0] + max(k[x][0],k[x][1] + w);
        if(mx1[x] < mx2[x]) {swap(mx1[x],mx2[x]);swap(son1[x],son2[x]);}
        solve(y,x);
    }
}
int main() {
    n = read();
    for(int a,b,c,i=1;i<n;i++) {
        a = read();b = read();c=read();
        G[a].push_back(pii(b,c));
        G[b].push_back(pii(a,c));
    }
    dfs(1,0);g[1][0] = f[1][0];
    solve(1,0);int ans = 0;
    for(int i = 1;i <= n;i++) ans = max(ans,g[i][0]);
    cout << ans << endl;
}