【题解】LuoGu4408：[NOI2003]逃学的小孩

原题传送门
本来想的一个$O(n^2)$的暴力
枚举$C$,把它记为根，在$dfs$枚举$lca(A,B)$
求出$fi{r}_u,se{c}_u$表示以$u$为根的子树中最长链，次长链
再记$d_u$为深度，那么对于一个$(C,lca(A,B))$的答案是$fi{r}_u+2se{c}_u+d_u$

其实可以只枚举$lca(A,B)$记为$D$好了，想要知道在$fi{r}_D,se{c}_D$已经有的情况下，最优的$C$在哪
对于每个点求出$fi{r}_u,se{c}_u,th{i}_u$，前三长的链，以及$idfi{r}_u$最长链对应的儿子编号
然后再$dfs$，如果走到最长链里面，即$v=idfi{r}_u$，则顺便传下去$se{c}_u+l$
否则传下去$fi{r}_u+l$
对于每个点$u$，我们知道了$fi{r}_u,se{c}_u,th{i}_u$，还知道了从上面传下来的$d$，这个$d$不只是暴力里面的深度，是根的最优情况
然后$max(th{i}_u,d)$就是根到点$u$的最优距离
然而最终的答案是$se{c}_u$要×个2，这个$se{c}_u$是中间大的
所以找出中间大的是×2的那个

Code：

#include <bits/stdc++.h>
#define maxn 200010
#define LL long long
using namespace std;
struct Edge{
	int to, next;
	LL len;
}edge[maxn << 1];
int num, head[maxn], n, m;
LL fir[maxn], sec[maxn], thi[maxn], ans, deg[maxn], rt, idfir[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; }

void dfs(int u, int pre){
	fir[u] = sec[u] = thi[u] = 0;
	idfir[u] = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		LL l = edge[i].len;
		if (v != pre){
			dfs(v, u);
			if (fir[v] + l > fir[u]){
				thi[u] = sec[u], sec[u] = fir[u], fir[u] = fir[v] + l, idfir[u] = v;
//				if (sec[v] + l > sec[u]) sec[u] = sec[v] + l;
			} else if (fir[v] + l > sec[u]) thi[u] = sec[u], sec[u] = fir[v] + l;
			else if (fir[v] + l > thi[u]) thi[u] = fir[v] + l;
		}
	}
//	ans = max(ans, fir[u] + sec[u] + sec[u] + max(d, thi[u]));
}

void dfs1(int u, int pre, LL d){
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		LL l = edge[i].len;
		if (v != pre){
			if (v == idfir[u]) dfs1(v, u, max(sec[u], d) + l);
			else dfs1(v, u, max(fir[u], d) + l);
		}
	}
	LL x = fir[u], y = sec[u], z = max(d, thi[u]);
	if (z > x) swap(z, x);
	if (y > x) swap(y, x);
	if (z > y) swap(z, y);
	ans = max(ans, x + y + y + z);
//  ans = max(ans, fir[u] + sec[u] + sec[u] + max(d, thi[u]));
//	printf("%d %d %d %d %d\n", u, fir[u], sec[u], thi[u], d);
}

int main(){
	freopen("pc.in", "r", stdin);
	freopen("pc.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read(), z = read();
		addedge(x, y, z), addedge(y, x, z);
		++deg[x], ++deg[y];
	}
	for (int i = 1; i <= n; ++i) if (deg[i] > 1) rt = i;
	dfs(rt, 0);
/*	for (int i = 1; i <= n; ++i){// printf("rt : %d\n", i);
		dfs(i, 0, 0);
	}*/
	dfs1(rt, 0, 0);
	printf("%lld\n", ans);
	return 0;
}