树是一种特殊的图结构,有根树是一个有固定根的树。
现在给定一棵有根树,编程求出树中所有节点到指定的根节点最远距离。
输入格式
第一行是两个整数 N,M,表示数的顶点数和根节点的编号。接下来 N−1 行,每行两个整数 u,v,表示编号为 u 的节点和编号为 v的节点间有一无向条边。
输出格式
输出距离根节点最远的点到根的距离。
数据范围
1≤N≤10000,
1≤M≤N,
1≤u,v≤N
输入样例:
5 5
1 2
1 4
1 5
2 3
输出样例:
3
#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,M=2*N;
int h[N],e[M],ne[M],idx;
int dis[N];
int n,m;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dis[j]=dis[u]+1;dfs(j,u);}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;add(a,b);add(b,a);}dfs(m,-1);int res=0;for(int i=0;i<n;i++)res=max(res,dis[i]);cout<<res;return 0;
}