树形dp思路

A 树的最长路径

对于树中的任意节点 a，它能到达的最远节点为 b，而 a 到 b 一定是一个。因此，树的直径长度等于 a 到 b 的最长路径与 a 到次长路径之和的最大值（遍历所有节点 u 后取最大）。

通过一次 DFS 计算每个节点的 “最长子树路径” 和 “次长子树路径”，两者之和的最大值就是树的直径。

#include<bits/stdc++.h>
using namespace std;
int n, f1[10005], f2[10005], res;
int h[10005], v[10005 << 1], w[10005 << 1], ne[10005 << 1], idx;
void add(int x, int y, int z) {
	v[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}
void dfs(int u, int fa) {
	f1[u] = f2[u] = 0;
	for(int i = h[u]; i != -1; i = ne[i]) {
		int j = v[i];
		if(j == fa) {
			continue;
		}
		dfs(j, u);
		if(f1[j] + w[i] >= f1[u]) {
			f2[u] = f1[u];
			f1[u] = f1[j] + w[i];
		} else if(f1[j] + w[i] > f2[u]) {
			f2[u] = f1[j] + w[i];
		}
	}
	res = max(res, f1[u] + f2[u]);
}
int main() {
	cin >> n;
	memset(h, -1, sizeof h);
	for(int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z);
	}
	dfs(1, -1);
	cout << res;
	return 0;
}

B 树的中心

树的中心具有这样的特性：从这个节点出发到树中最远节点的距离，是所有的节点中最近的。

所以我们可以先选择任意节点，然后进行两次深度DFS:

第一次 DFS ： 计算出当前子树的结点对当前结点的贡献和每个节点向子树方向的最长路径与次长路径(因为不能走回头路)。

第二次 DFS ： 计算每个节点与父节点的最长路径。

#include<bits/stdc++.h>
using namespace std;
int n, s[10005], idx;
int d1[10005], d2[10005], f1[10005], f2[10005];
int h[10005], v[10005 << 1], w[10005 << 1], ne[10005 << 1];
void add(int a, int b, int c) {
	v[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dfs1(int u, int fa) {
	for(int i = h[u]; i != -1; i = ne[i]) {
		if(v[i] == fa) continue;
		dfs1(v[i], u);
		if(d1[v[i]] + w[i] >= d1[u]) {
			d2[u] = d1[u];
			f2[u] = f1[u];
			d1[u] = d1[v[i]] + w[i];
			f1[u] = v[i];
		} else if(d1[v[i]] + w[i] > d2[u]) {
			d2[u] = d1[v[i]] + w[i];
			f2[u] = v[i];
		}
	}
}
void dfs2(int u, int fa) {
	for(int i = h[u]; i != -1; i = ne[i]) {
		if(v[i] == fa) {
			continue;
		}
		if(f1[u] == v[i]) {
			s[v[i]] = w[i] + max(s[u], d2[u]);
		} else {
			s[v[i]] = w[i] + max(s[u], d1[u]);
		}
		dfs2(v[i], u);
	}
}
int main() {
	memset(h, -1, sizeof h);
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	dfs1(1, -1);
	dfs2(1, -1);
	int res = 0x3f3f3f3f;
	for(int i = 1; i <= n; i++) {
		res = min(res, max(d1[i], s[i]));
	}
	cout << res;
	return 0;
}