• https://www.luogu.com.cn/problem/P3647
• https://oj.uz/problem/view/APIO14_beads

无根树不太好设计状态，想办法转成有根树，然后用子树替换大法。
再跑换根 dp。
我永远爱宏。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e5) + 9;

int d[N][2], e[N][2], z;
VII adj[N];
int n;

#define dv (max(d[v][0], d[v][1] + w))
#define tv ((d[v][0] + w) - dv)
#define dp (max(e[u][0], e[u][1] + pw))
#define tp ((e[u][0] + pw) - dp)

void dfs1(int u = 1, int p = 0) {
    int t = -INF;
    for (auto _: adj[u]) {
        int v = _.fi; if (v == p) continue; int w = _.se;
        dfs1(v, u); d[u][0] += dv;
        checkMax(t, tv);
    }
    d[u][1] = d[u][0] + t;
}

void dfs2(int u = 1, int p = 0, int pw = -INF) {

    checkMax(z, d[u][0] + dp);

    int t0 = tp, t1 = -INF, v0 = -1;
    for (auto _: adj[u]) {
        int v = _.fi; if (v == p) continue; int w = _.se;   if (tv > t0) t1 = t0, t0 = tv, v0 = v;
        else if (tv > t1) t1 = tv;
    }

    for (auto _: adj[u]) {
        int v = _.fi; if (v == p) continue; int w = _.se;
        e[v][0] = d[u][0] - dv + dp;
        e[v][1] = e[v][0] + (v0 == v ? t1 : t0);
        dfs2(v, u, w);
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    DO(RD(n)-1) {
        int x, y, w; RD(x, y, w);
        adj[x].PB({y,w});
        adj[y].PB({x,w});
    }

    dfs1(); dfs2();
    cout << z << endl;
}

Posted by xiaodao
Category: 日常