嘟嘟嘟



这题刚开始想复杂了，想什么dp去了，其实没那么难。

考虑断掉一条边，记分离出来的两棵子树为A和B，那么合并后的树的直径可能有三种情况：

1.A的直径。

2.B的直径

3.A的半径+边权+B的半径。

半径是啥？记从点\(i\)出发到树上任意一点的最长距离为\(f[i]\)，则树的半径就是\(min \{ f[i] \}\)（此题需要min，严格定义我也不知道是max还是min）。



所以我们\(O(n)\)枚举断边，\(O(n)\)求树的直径和半径即可。

直径不必说，说一下怎么求半径。

对于点\(v\)，记\(v\)的父亲为\(u\), \(v\)的半径有这么几种情况：

1.\(v\)子树内的最长链。

2.\(v\)子树外，\(u\)子树内的一条链 + \(dis(u, v)\)。

3.\(u\)子树外的最长链 + \(dis(u, v)\)。

对于情况1，求树的直径的时候就维护好了。

对于情况2，我们需要维护最长连和次长链。然后如果\(v\)在\(u\)的最长链上，就是\(u\)的次长链 + \(dis(u, v)\)；否则就是\(u\)的最长链 + \(dis(u, v)\)。

对于情况3，在dfs的时候维护一个fro，表示\(u\)子树外的最长链，维护fro的时候也向情况2分两种情况，分别更新即可。



答案就是所以直径的min。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 5e3 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n;

struct Node

{

  int x, y, w;

}t[maxn];

struct Edge

{

  int nxt, to, w;

}e[maxn << 1];

int head[maxn], ecnt = -1;

In void addEdge(int x, int y, int w)

{

  e[++ecnt] = (Edge){head[x], y, w};

  head[x] = ecnt;

}

bool col[maxn];

int dp1[maxn], dp2[maxn], dia_Max = 0;

In void dfs(int now, int _f, int c)

{

  dp1[now] = 0, col[now] = c;

  int Max1 = 0, Max2 = 0;

  for(int i = head[now], v; ~i; i = e[i].nxt)

    {

      if((v = e[i].to) == _f) continue;

      dfs(v, now, c);

      if(dp1[v] + e[i].w > Max1) Max2 = Max1, Max1 = dp1[v] + e[i].w;

      else if(dp1[v] + e[i].w > Max2) Max2 = dp1[v] + e[i].w;

    }

  dp1[now] = Max1; dp2[now] = Max2;

  dia_Max = max(dia_Max, Max1 + Max2);

}

int f[maxn];

In void dfs2(int now, int _f, int fro)

{

  int tp = 0;

  for(int i = head[now], v; ~i; i = e[i].nxt)

    {

      if((v = e[i].to) == _f) continue;

      if(dp1[v] + e[i].w == dp1[now])

	{

	  f[v] = max(dp1[v], dp2[now] + e[i].w);

	  tp = max(dp2[now], fro);

	}

      else

	{

	  f[v] = max(dp1[v], dp1[now] + e[i].w);

	  tp = max(dp1[now], fro);

	}

      f[v] = max(f[v], tp + e[i].w);

      dfs2(v, now, tp + e[i].w);

    }

}

int main()

{

  Mem(head, -1);

  n = read();

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

    {

      int x = read(), y = read(), w = read();

      t[i] = (Node){x, y, w};

      addEdge(x, y, w), addEdge(y, x, w);

    }

  int ans = INF;

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

    {

      dia_Max = 0;

      dfs(t[i].x, t[i].y, 0), dfs(t[i].y, t[i].x, 1);

      f[t[i].x] = dp1[t[i].x], f[t[i].y] = dp1[t[i].y];

      dfs2(t[i].x, t[i].y, 0), dfs2(t[i].y, t[i].x, 0);

      int pos1 = t[i].x, pos2 = t[i].y;

      for(int j = 1; j <= n; ++j)

	{

	  if(!col[j] && f[j] < f[pos1]) pos1 = j;

	  if(col[j] && f[j] < f[pos2]) pos2 = j;

	}

      ans = min(ans, max(dia_Max, f[pos1] + f[pos2] + t[i].w));

    }

  write(ans), enter;

  return 0;

}