牛客小白月赛6 桃花

桃花"/>

牛客小白月赛6 桃花

链接：
来源：牛客网
 

时间限制：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
数据量较大，注意使用更快的输入输出方式。

#pragma GCC optimize ("O3")
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1000005
using namespace std;
vector<int> v[MAXN];
bool vis[MAXN];
int n,d1[MAXN],d2[MAXN],fa[MAXN];
void read(int &x){char ch = getchar(); x = 0;while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
}
void init(int _n)
{n=_n;for(int i=1;i<=n;++i) v[i].clear();memset(d1,0,n*sizeof(int));memset(d2,0,n*sizeof(int));
}void add(int a,int b)
{v[a].push_back(b);v[b].push_back(a);
}void father(int x,int f)
{fa[x]=f;vis[x]=true;for(int i=0;i<v[x].size();++i){if(!vis[v[x][i]]) father(v[x][i],x);}
}void solve(int x)
{vis[x]=true;for(int i=0;i<v[x].size();++i){if(!vis[v[x][i]]) solve(v[x][i]);}int temp;for(int i=0;i<v[x].size();++i){if(v[x][i]!=fa[x]&&d1[x]<d1[v[x][i]]+1){d1[x]=d1[v[x][i]]+1;temp=v[x][i];}}for(int i=0;i<v[x].size();++i){if(v[x][i]!=fa[x]&&v[x][i]!=temp&&d2[x]<d1[v[x][i]]+1){d2[x]=d1[v[x][i]]+1;}}
}int main()
{int n,a,b;read(n);init(n);for(int i=0;i<n-1;++i){read(a);read(b);add(a,b);}memset(vis,0,n);father(1,-1);memset(vis,0,n);solve(1);int ans=0;for(int i=1;i<=n;++i) ans=max(ans,d1[i]+d2[i]);printf("%d\n", ans + 1);
}