题目链接
题解
枚举断开哪一条边，然后对剩余的两棵树分别做一遍换根法树形dp
需要求出每个点到树中其它点距离的最大值\(f[i]\)和次大值\(g[i]\)【用以辅助换根计算最大值】
求出每棵树中的最长路径，然后再将两棵树中\(f[i]\)最小值相连保证相连后产生的最大值最小
\(O(n^2)\)的复杂度
如果怕被卡常，可以知道要切的边一定在直径上，虽然上界没有变，但速度可以快不少
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 5005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int h[maxn],ne = 1;
struct EDGE{int from,to,nxt,w,flag;}ed[maxn << 1];
inline void build(int u,int v,int w){
ed[++ne] = (EDGE){u,v,h[u],w,1}; h[u] = ne;
ed[++ne] = (EDGE){v,u,h[v],w,1}; h[v] = ne;
}
int f[maxn],g[maxn],ch[maxn],d[maxn],du,path[maxn],fa[maxn];
int n,ans,fans,mnans;
void DFS(int u,int Fa){
if (d[u] > d[du]) du = u;
Redge(u) if ((to = ed[k].to) != Fa){
d[to] = d[u] + ed[k].w; path[to] = k;
DFS(to,u);
}
}
void dfs(int u){
f[u] = g[u] = 0;
Redge(u) if (ed[k].flag && (to = ed[k].to) != fa[u]){
fa[to] = u; d[to] = ed[k].w; dfs(to);
if (f[to] + ed[k].w > f[u]){
g[u] = f[u];
f[u] = f[to] + ed[k].w;
ch[u] = to;
}
else if (f[to] + ed[k].w > g[u]) g[u] = f[to] + ed[k].w;
}
fans = max(fans,f[u]);
}
void dfs2(int u){
if (fa[u]){
int v = fa[u];
if (ch[v] == u){
if (g[v] + d[u] > f[u]){
g[u] = f[u];
f[u] = g[v] + d[u];
ch[u] = v;
}
else if (g[v] + d[u] > g[u]) g[u] = g[v] + d[u];
}
else {
if (f[v] + d[u] > f[u]){
g[u] = f[u];
f[u] = f[v] + d[u];
ch[u] = v;
}
else if (f[v] + d[u] > g[u]) g[u] = f[v] + d[u];
}
}
Redge(u) if (ed[k].flag && (to = ed[k].to) != fa[u]){
dfs2(to);
}
fans = max(fans,f[u]);
mnans = min(mnans,f[u]);
}
int dp(int rt){
d[rt] = 0; fa[rt] = 0; dfs(rt);
mnans = INF;
dfs2(rt);
return mnans;
}
int main(){
n = read(); int a,b,w; ans = INF;
for (int i = 1; i < n; i++){
a = read(); b = read(); w = read();
build(a,b,w);
}
d[du = 1] = 0; DFS(1,0);
path[du] = 0; d[du] = 0; DFS(du,0);
int t1,t2;
for (int i = du; path[i]; i = ed[path[i]].from){
int k = path[i];
ed[k].flag = ed[k ^ 1].flag = false;
cls(f); cls(g); fans = 0;
t1 = dp(ed[k].from);
t2 = dp(ed[k].to);
//REP(j,n) printf("%d ",f[j]); puts("");
fans = max(fans,t1 + t2 + ed[k].w);
//printf("(%d,%d) mx = %d\n",ed[k].to,ed[k].from,fans);
ans = min(ans,fans);
ed[k].flag = ed[k ^ 1].flag = true;
}
printf("%d\n",ans);
return 0;
}