关于dfs_d 和 dfs_u 的递归放置顺序 做出详细解释
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 2 * N;
int n, maxd; // maxd记录树的直径
int h[N], e[M], ne[M], idx; // 因为是无向图,每个点可能连接两个点,所以取M
int d1[N], d2[N], up[N], p1[N]; // d1[i]记录i向下走的最大长度,d2[i]记录i向下走的次大长度,up[i]记录i往上走的最大长度 p1存下u节点往下最大路走的子节点
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs_d(int u, int father)
{
for(int i = h[u]; i != -1; i = ne[i]){ // 遍历u的每一条出边
int j = e[i];
if(j != father){
dfs_d(j, u); // 先算出子结点的d1和d2 才能更新父节点 所以先递归 =>自下而上的过程
int distance = d1[j] + 1;
if(distance > d1[u]){
d2[u] = d1[u], d1[u] = distance;
p1[u] = j;
}
else if(distance > d2[u]){
d2[u] = distance;
}
}
}
maxd = max(maxd, d1[u] + d2[u]);
}
void dfs_u(int u, int father)
{
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j != father){
up[j] = up[u] + 1;
if(p1[u] == j) up[j] = max(up[j], d2[u] + 1);
else up[j] = max(up[j], d1[u] + 1);
dfs_u(j, u); // 先计算父结点的up值,才能算子节点的 =>自上而下的过程,故后递归
}
}
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b); // 无向图,所以加两条边
add(b, a);
}
dfs_d(0, -1); // 求每个点的d1和d2 从结点0开始搜索,其父节点为-1
dfs_u(0, -1); // 求每个点的up值
// 取d1 d2 up中最大的两个值
for(int i = 0; i < n; i++){
int d[3] = {d1[i], d2[i], up[i]};
sort(d, d + 3);
if(d[1] + d[2] == maxd) printf("%d\n", i);
}
return 0;
}