题意：给出一棵无向树，求树的直径，即树上两点之间的最长距离
分析：两种解法
解法1：先任取一个点，找到距离该点最远的点u，再找到距离u最远的点v，那么u和v之间的路径就是一条直径。
证明：只要找到了树的直径的一个端点，再从该点找到最远点就一定是直径的另一个端点。所以只需要证明第一次找到的最远点u就是其中一个端点即可。
上述证明过程建立在所有路径均不为负的前提下，如果树上存在负权边，则上述证明不成立。
点击查看代码
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
struct T {
int v, w, nx;
} g[N];
int h[N], idx, temp, ans;
void add(int u, int v, int w) {
g[++idx] = {v, w, h[u]}, h[u] = idx;
}
bool st[N];
void dfs(int u, int s) {
st[u] = 1;
if (ans < s)
temp = u, ans = s;
for (int i = h[u]; i; i = g[i].nx) {
int v = g[i].v, w = g[i].w;
if (!st[v])
dfs(v, s + w);
}
}
int main() {
int x, y, z;
while (cin >> x >> y >> z) {
add(x, y, z), add(y, x, z);
}
dfs(1, 0);
memset(st, 0, sizeof(st)), dfs(temp, 0);
cout << ans;
return 0;
}
解法2：树形dp，枚举根节点，找最大和次大子树
无论边权正负均可
点击查看代码
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
struct T {
int v, w, nx;
} g[N];
int h[N], idx, ans;
void add(int u, int v, int w) {
g[++idx] = {v, w, h[u]}, h[u] = idx;
}
int dfs(int u, int fu) {
int dist = 0, d1 = 0, d2 = 0;// d1,d2: 最大,次大
for (int i = h[u]; i; i = g[i].nx) {
int v = g[i].v, w = g[i].w;
if (fu == v) continue;
int d = dfs(v, u) + w;
dist = max(dist, d);
if (d >= d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;
}
ans = max(ans, d1 + d2);
return dist;
}
int main() {
int x, y, z;
while (cin >> x >> y >> z) {
add(x, y, z), add(y, x, z);
}
dfs(1, -1);
cout << ans;
return 0;
}