题意抽象,给定一颗树,找到该树中以根节点为端点的最长路径,也就是树的直径
提高课原题,这里来推一下性质和思路
寻找树的具体直径的思路
$\quad$1.从任意一点出发(通常直接从根节点出发),找到距离该点最远的点u
$\quad$2.从点u出发,找到距离点u最远的一个点t,dist(u,t)则为树的直径
(简化版)求树的直径的长度的思路
$\quad$将每条最长路径所经过的最高的点x作为该路径的标记,故路径可分为两种情况:
$\quad$$\quad$1.x点是该最长路径的端点,则经过该点的最长路径就是x的子树中的最大深度
$\quad$$\quad$2.x点是该最长路径的中间点,则经过该点的最长路径就是x的子树中的最大深度和次大深度的和
$\quad$因为本题只需输出树的最长路径的长度,无需输出具体路径,所以直接实现简化版的代码即可
#include <bits/stdc++.h>
using namespace std;
const int N=30010,M=2*N;
int h[N], e[M], ne[M], idx;
int n,m;
int ans;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u,int father){
int d1=0,d2=0;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father) continue;
int d=dfs(j,u)+1;
if(d>=d1) d2=d1,d1=d;
else if(d>=d2) d2=d;
}
ans=max(ans,d1+d2);
return d1;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for(int i=2;i<=n+m;i++){
int x;
scanf("%d",&x);
add(x,i);
add(i,x);
}
dfs(1,-1);
cout<<ans;
return 0;
}