Description：

给一棵边带权的树，可以删掉一条边，再加上一条同等权值的边，最小化最后的树的直径。

$1\leqslant n\leqslant 5000$

Solution：

$O(n^2)$ 卡卡常可过。

先枚举删那条边，然后最后的答案一定是分成的两棵子树的直径或加上这条边后包含这条边的最长路其中之一，两棵子树的直径可以树形 $DP$ 求，不难发现这条边一定连在两棵子树的到其他点距离的最大值最小的点上，这个可以在刚才的树形 $DP$ 中一并求出，方法就是类似 COGS1359 最长链 的做法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 5010

struct edges

{

	int u,v,w;

}es[MAXN];

struct edge

{

	int to,nxt,v,id;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

bool ava[MAXN];

inline void add(int a,int b,int c,int id)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].id = id;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].id = id;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

#define mp make_pair

int f[MAXN],g[MAXN];

bool v[MAXN];

int res[MAXN];

void dp1(int k)

{

	v[k] = true;f[k] = 0;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to] && ava[e[i].id])

		{

			dp1(e[i].to);

			f[k] = max(f[k],f[e[i].to] + e[i].v);

		}

	}

	v[k] = false;

	return;

}

void dp2(int k)

{

	v[k] = true;

	register int maxf = -1,bel,val;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

		if(!v[e[i].to] && ava[e[i].id])

			g[e[i].to] = g[k] + e[i].v;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to] && ava[e[i].id])

		{

			if(f[e[i].to] + e[i].v > maxf)

			{

				maxf = f[e[i].to] + e[i].v;

				bel = e[i].to;val = e[i].v;

			}

		}

	}

	for(register int i = lin[k];i != 0;i = e[i].nxt)

		if(!v[e[i].to] && ava[e[i].id] && e[i].to != bel)

			g[e[i].to] = max(g[e[i].to],maxf + e[i].v);

	for(register int i = lin[k];i != 0;i = e[i].nxt)

		if(!v[e[i].to] && ava[e[i].id] && e[i].to != bel)

			g[bel] = max(g[bel],f[e[i].to] + e[i].v + val);

	for(register int i = lin[k];i != 0;i = e[i].nxt)

		if(!v[e[i].to] && ava[e[i].id])

			dp2(e[i].to);

	return;

}

inline int getd()

{

	int ans = 0;

	for(int i = 1;i <= n;++i)ans = max(ans,res[i]);

	return ans;

}

inline int getrt(int s)

{

	dp1(s);

	g[s] = 0;

	dp2(s);

	register int rt = 0;res[0] = 0x3f3f3f3f;

	for(register int i = 1;i <= n;++i)

	{

		if(v[i])

		{

			res[i] = max(f[i],g[i]);

			if(res[i] < res[rt])rt = i;

			v[i] = false;

		}

	}

	return rt;

}

int main()

{

	n = rd();

	for(register int i = 1;i < n;++i)

	{

		es[i].u = rd();es[i].v = rd();

		es[i].w = rd();

		add(es[i].u,es[i].v,es[i].w,i);

		ava[i] = true;

	}

	register int ans = 0x3f3f3f3f;

	for(register int i = 1;i < n;++i)

	{ 

		ava[i] = false;

		register int r1 = getrt(es[i].u),r2 = getrt(es[i].v);

		ans = min(ans,max(getd(),res[r1] + res[r2] + es[i].w));

		ava[i] = true;

	}

	cout << ans << endl;

	return 0;

}