桃花
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
桃花一簇开无主，可爱深红映浅红。
——《题百叶桃花》
桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。
输入描述:
第一行有一个正整数n，表示桃树的节点个数。 接下来n-1行，第i行两个正整数ai,bi ，表示桃树上的节点ai,bi之间有一条边。
输出描述:
第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。
示例1
输入
复制
3 1 2 2 3
输出
复制
3
示例2
输入
复制
3 1 2 1 3
输出
复制
3
示例3
输入
复制
4 1 2 2 3 3 4
输出
复制
4
备注:
对于100%的测试数据： 1 ≤ n ≤ 1000000 数据量较大，注意使用更快的输入输出方式。
链接：https://ac.nowcoder.com/acm/problem/17362
题意：求最长的一条线。
题解：树的直径，先随机找一点开始dfs到最远的点，然后从最远的点dfs到另一个最远的点。
#include <stdio.h>
#include <vector>
using namespace std;
vector<int>maps[1000000];
bool book[1000000];
int maxlen,maxnode;
int read()
{
char ch=getchar();
int x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void dfs(int node,int len)
{
if(len>maxlen)
{
maxlen=len;
maxnode=node;
}
for(int i=0;i<maps[node].size();++i)
{
if(book[maps[node][i]]==false)
{
book[maps[node][i]]=true;
dfs(maps[node][i],len+1);
book[maps[node][i]]=false;
}
}
}
int main()
{
int n,l,r;
n=read();
for(int i=1;i<n;++i)
{
l=read(),r=read();
maps[l].push_back(r);
maps[r].push_back(l);
}
book[1]=true;
dfs(1,1);
book[1]=false;
book[maxnode]=true;
dfs(maxnode,1);
printf("%d",maxlen);
return 0;
}
