Original link: https://www.shuizilong.com/house/archives/luogu-p3647-apio2014-%E8%BF%9E%E7%8F%A0%E7%BA%BF/
The unrooted tree is not in a good design state. Find a way to convert it into a rooted tree, and then replace Dafa with a subtree.
Then run and change the root dp.
I love macros forever.
#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;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p3647-apio2014-%E8%BF%9E%E7%8F%A0%E7%BA%BF/
This site is only for collection, and the copyright belongs to the original author.