笔记:
C++代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010,M=N*2;
int h[N], e[M], ne[M], idx;
int n,maxd;
int d1[N],d2[N],up[N],p1[N];//总结:求树的直径时,只需dfs_d,定义两个d1,d2数组,分别存储每个节点向下走的最长路径的长度和次长路径的长度。
//所有结点的最长路径和次长路径之和的最大值就是树的直径
//如果还要求树的直径上的所有点,还要dfs_u,定义一个up数组,表示每个节点向上走能走的最远距离
//p1数组表示每一个节点向下的最长路径所经过的直接子节点。
//更新方式为:dfs_u,画个图一目了然
void add(int a, int b) // 添加一条边a->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])
{
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;//退而求其次,hh
}
}
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;//up数组和父节点有关,这一步一定要写。
if(p1[u]==j) //说明从j向下走是从u向下走最长路径
{
up[j]=max(up[j],d2[u]+1);//用第二长的路径更新up数组
}
else up[j]=max(up[j],d1[u]+1);//说明从j向下走不是从u向下走的最长路径,用最长的路径更新up数组
dfs_u(j,u);//从上往下算
}
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
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);//习惯上以0为根节点,但其实任意一点都可以,传入父节点防止往回搜
dfs_u(0,-1);
for(int i=0;i<n;i++)
{
int dx[3]={d1[i],d2[i],up[i]};
sort(dx,dx+3);
if(dx[2]+dx[1]==maxd) printf("%d\n",i);
//if(d1[i]+up[i]==maxd) printf("%d\n",i);//不能这么写,会落下根节点
}
return 0;
}
疑问:
dfs_u时,如果向下走的最大路径和次大路径都先经过j这个点怎么办?
解答:经过某一个儿子节点的路径不可能既是最大值,又是次大值
想问一下 //if(d1[i]+up[i]==maxd) printf(“%d\n”,i);//不能这么写,会落下根节点
这是为什么,为什么这样写会落下?而且我有点不理解为什么算经过哪些点需要up数组
最大路径和次大路径有可能同时经过同一个儿子节点啊,解答稍微有点没看懂hh
虽然说凭空想象可能会出现最长路径和次长路径都经过同一个子节点(j这个节点)的情况,但是要分析代码的过程:
dfs_d这个函数中,每次d1,d2的更新是以u的每一个子节点为单位的,j作为u的一个子节点,distance(d1[j]+1)要么更新d1[u],要么更新d2[u],要么二者都不更新;
如果distance更新了d1[u],那么走到j这个子节点就是最长路径,d2[u]不会被distance更新,所以次长路径一定是走到了其它的子节点上
okk,完全明白了,谢谢大佬(・ω・)
客气了