牛客網 桃花（樹的直徑）

桃花

時間限制：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;
}