思路可参考:
https://www.acwing.com/solution/content/8986/
注意:向上搜的情况较难理解,这里可以参考上述链接中大佬给出的图。
这里给出上述图的测试数据,可结合下述注释代码打印结果,增进理解。
输入:
8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
输出:
0
1
2
3
5
6
7
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10, M = 2*N;
int h[N], e[M], ne[M], idx;
int p1[N], d1[N], d2[N], up[N];//d1[i],d2[i]分别为从i点向下的最长和次长路径, up[i]为i点向上的最长路径
int maxn;
void add(int a, int b)
{
e[idx]=b, ne[idx]=h[a], h[a]=idx++; //图的邻接表存储,基础课里有
}
// 最大长度有两种情况: 1.向下的最长边和次长边的和 2. 向上的最长边和向下的最长边的和
//从该点向下搜
void dfs_d(int u, int father) //dfs往下走的路径的次大值和最大值
{
for(int i=h[u]; i!=-1; i=ne[i])
{
int j=e[i];
if(j!=father)
{
dfs_d(j, u);
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;
}
}
}
maxn = max(maxn, d1[u]+d2[u]); //每条路径必然存在最高点,在最高点计算的d1 + d2就是最长路径。
}
//从该点向上搜
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(j==p1[u]) up[j] = max(up[j], d2[u]+1); //若j在u的最长路径上(则不可取d1[u]),则取次长路径
else up[j] = max(up[j], d1[u]+1); //j不在最长路径上
dfs_u(j,u);
}
}
}
int main()
{
int n;
cin>>n;
memset(h, -1, sizeof h);
for(int i=0; i<n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a,b), add(b,a);
}
//开始搜的点只要在树中即可,不一定要从0开始
dfs_d(2, -1); //这里初始父结点可设为任意不在树中的值
dfs_u(2, -1);
for (int i = 0; i < n; i ++ )
{
//下面一行注释可以用来测试,通过打印各数组的值来加深理解
//printf("%d : d1[i]:%d,d2[i]:%d, up[i]:%d\n",i, d1[i], d2[i], up[i]);
int d[3] = {d1[i], d2[i], up[i]};
sort(d, d + 3);
if (d[1] + d[2] == maxn) printf("%d\n", i);
}
return 0;
}