请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。这个点被称为树的中心。

题解：https://www.cnblogs.com/dx123/p/17302104.html
评测：https://www.acwing.com/problem/content/1075/
暴力做法是以每个点为根，求出从根向下走的最远距离，这个过程需要做n遍，每一遍dfs的复杂度是O（n),时间复杂度是O（n^2),考虑优化。

https://oi-wiki.org/dp/tree/#换根-dp

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。

算法讲解：
第一次dfs和求树的直径的时候一样，通过递归从下而上得到从 u点向下走的最远距离，根据题目我们还需要将这个答案去和u点向上走的距离去比较。
在第二次dfs中，我们需要充分利用第1次dfs的信息，对于当前的点j，它的父节点是u。
第二次的dfs是从上而下类似拓扑序去更新的。

  • 如果j在u的下最长路，那么j的上最长路需要考虑是 j与u的距离+max（u的下次长路，u的上最长路）
  • 如果j不在u的下最路，那么j的上最长路需要考虑是 j与u的距离+max（u的下最长路，u的上最长路）

根据这个过程我们知道，在第一次dfs过程中需要多维护两个数组，每个点的下次长距离 和 自己的长链意义下的重儿子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N=20010;
int n,a,b,c,ans=2e9;
struct edge{int v,w;};
vector<edge> e[N];
int d1[N],d2[N],path[N],up[N];
//path数组就是自己的长链意义下的重儿子
//d2[N]记录每个点的下次长距离
void dfs(int x,int fa){
  for(auto ed : e[x]){
    int y=ed.v, z=ed.w;
    if(y==fa) continue;
    dfs(y, x);
    if(d1[y]+z>d1[x]) 
      d2[x]=d1[x],d1[x]=d1[y]+z,path[x]=y;
    else if(d1[y]+z>d2[x]) d2[x]=d1[y]+z;
  }
}
void dfs2(int x,int fa){
  for(auto ed : e[x]){
    int y=ed.v, z=ed.w;
    if(y==fa) continue;
    if(y==path[x])up[y]=max(up[x],d2[x])+z;
    else up[y]=max(up[x],d1[x])+z;
    dfs2(y, x);
  }
}
int main(){
  cin>>n;
  for(int i=1; i<n; i++){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  dfs(1, 0);
  dfs2(1, 0);
  for(int i=1; i<=n; i++)
    ans=min(ans,max(d1[i],up[i]));//最后直接求每个点的最大距离，然后求min
  cout<<ans;
}