链接：https://www.nowcoder.com/acm/contest/136/C
来源：牛客网
桃花
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
桃花一簇开无主，可爱深红映浅红。
——《题百叶桃花》
桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。
输入描述:
第一行有一个正整数n，表示桃树的节点个数。
接下来n-1行，第i行两个正整数a
i
,b
i
，表示桃树上的节点a
i
,b
i
之间有一条边。
输出描述:
第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。
输入例子:
3
1 2
2 3
输出例子:
3
-->
备注:
对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。 解题思路：求树直径的裸题，两遍dfs，第⼀遍从任⼀点开始，找到距这个点最远的点，他⼀定是直径的⼀端，然 后从这个点开始再dfs，找到最远的距离，输出即可。可以用DFS，也可以用BFS，节点数比较多，需要用链式前向星的方法存储边。
DFS代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
struct node{
int to,next;
}edge[*maxn];
int cnt=;
int vis[maxn],head[maxn],dis[maxn]; void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
} void dfs(int x)
{
vis[x]=;
for(int i=head[x];i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
dis[edge[i].to]=dis[x]+;
dfs(edge[i].to);
}
}
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dis[]=;
dfs();
int pos=;
for(int i=;i<=n;i++)
{
if(dis[i]>dis[pos])
pos=i;
}
memset(vis,,sizeof(vis));
dis[pos]=;
dfs(pos);
int ans=;
for(int i=;i<=n;i++)
{
if(dis[i]>ans)
ans=dis[i];
}
printf("%d\n",ans);
}
}
BFS代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
struct node{
int to,next;
}edge[*maxn];
int cnt=,ans;
int vis[maxn],head[maxn],dis[maxn];
queue<int> que; void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
} int bfs(int x)
{
memset(vis,,sizeof(vis));
dis[x]=;
que.push(x);
while(!que.empty())
{
int p=que.front();
que.pop();
for(int i=head[p];i!=-;i=edge[i].next)
{
if(!vis[edge[i].to])
{
dis[edge[i].to]=dis[p]+;
que.push(edge[i].to);
vis[edge[i].to]=;
ans=max(ans,dis[edge[i].to]);
}
}
}
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(head,-,sizeof(head));
memset(dis,,sizeof(dis));
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
ans=;
bfs();
int pos=;
for(int i=;i<=n;i++)
{
if(dis[i]>dis[pos])
pos=i;
}
ans=;
bfs(pos);
printf("%d\n",ans);
}
return ;
}