E91 换根DP P3647 APIO2014 连珠线

// 换根DP O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int read()
{
    int x = 0, f = 1;
    char s = getchar();
    while (s > '9' || s < '0')
    {
        if (s == '-')
            f = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9')
    {
        x = x * 10 + s - '0';
        s = getchar();
    }
    return x * f;
}
typedef long long LL;
const int N = 200005;
struct E
{
    int v, w;
};
vector<E> e[N];
int n, son[N];
LL mx[N], mx2[N], d[N], ans;
LL f[N][2], g[N][2], h[N][2];

void dfs(int u, int fa)
{
    mx[u] = mx2[u] = -2e9;
    for (E i : e[u])
    {
        int v = i.v, w = i.w;
        if (v == fa)
            continue;
        d[v] = w;
        dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1] + w);
        LL t = f[v][0] + w - max(f[v][0], f[v][1] + w);
        if (mx[u] < t)
            mx2[u] = mx[u], mx[u] = t, son[u] = v;
        else if (mx2[u] < t)
            mx2[u] = t;
    }
    f[u][1] = f[u][0] + mx[u];
}
void dfs2(int u, int fa)
{
    for (E i : e[u])
    {
        int v = i.v, w = i.w;
        if (v == fa)
            continue;
        h[u][0] = g[u][0] - max(f[v][0], f[v][1] + w);
        h[u][1] = h[u][0] + (son[u] == v ? mx2[u] : mx[u]);
        if (fa != 0)
        {
            LL t = h[fa][0] + d[u] - max(h[fa][0], h[fa][1] + d[u]);
            h[u][1] = max(h[u][1], h[u][0] + t);
        }
        g[v][0] = f[v][0] + max(h[u][0], h[u][1] + w);
        dfs2(v, u);
    }
}
int main()
{
    n = read();
    for (int i = 1; i < n; ++i)
    {
        int x = read(), y = read(), z = read();
        e[x].push_back({y, z});
        e[y].push_back({x, z});
    }
    dfs(1, 0);
    g[1][0] = f[1][0];
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i)
        ans = max(ans, g[i][0]);
    printf("%lld", ans);
}