概念：什么是树的直径

树上距离最远的两个点所连接的路径，叫做树的直径，显而易见的，一个树可以有多个直径。

实现：怎么写树的直径

Dfs深搜两遍

思路很简单，直接去找最远的两个点。先从任意点开始，找到距离他最远的点，记作 $x$ ；然后从 $x$ 开始找最远的点，记作 $y$ 。$x$ 和 $y$ 连接后的路径就是直径。但是这种深搜的做法无法解决负边权的树。

#include<bits/stdc++.h>
using namespace std;

int n;
vector<pair<int , int > >e[30010];

int dis[30010], vis[30010];

void Input(){
	scanf("%d",  &n);
	int u, v, w;
	for(int i=1; i<n; i++){
		scanf("%d%d%d", &u, &v, &w);
		e[u+1].push_back(make_pair(v+1, w));
		e[v+1].push_back(make_pair(u+1, w));
	}
}	

void Dfs(int x){
	vis[x]=1;
	for(auto &p:e[x]){
		if(vis[p.first]) continue;
		dis[p.first]=dis[x]+p.second;
		Dfs(p.first);
	}
}

void Work(){
	vis[1]=1;
	Dfs(1);
	int x=1;
	for(int i=1; i<=n; i++){
		if(dis[i]>dis[x]) x=i;
	}
	memset(dis, 0, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	vis[x]=1;
	Dfs(x);
	x=1;
	for(int i=1; i<=n; i++){
		if(dis[i]>dis[x]) x=i;
	}
	printf("%d", dis[x]);
}

int main(){
	Input();
	Work();
	return 0;
}

树形DP

我们记录当 $1$ 为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度 $d_1$ 与次长路径（与最长路径无公共边）长度，$d_2$ 那么直径就是对于每一个点，该点 $d_1 + d_2$ 能取到的值中的最大值。

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}