---

树的直径：树中所有最短路径的最大值。（1）树状dp（得到直径值）；（2）若无负权边，2次DFS（BFS）得到直径值和最长链)

（1）在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。

（2）树的直径，等于以树直径上任意一点为根的有根树，其左子树的高度+1，再加上其右子树高度+1。

dfs:

#include<iostream>
using namespace std;
const int N = 1010;
int h[N], next_pos[N], e[N], w[N], n, m, ans, p, idx;
int d[N];//d[i]表示从起点到i点的最长距离
void add(int a, int b, int c){
	e[++idx] = b;
	w[idx] = c;
	next_pos[idx] = h[a];
	h[a] = idx;
}

void dfs(int x, int father){
	if (ans < d[x]){
		ans = d[x];
		p = x;
	}
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (j == father){ continue; }
		d[j] = d[x] + w[i];
		dfs(j, x);
	}
}

void find(int x){
	ans = 0;
	d[x] = 0;
	dfs(x, 0);
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
	}

	find(1);
	find(p);
	cout << ans << endl;
	
	return 0;
}

（2）树状dp

#include<iostre...