NC17362. 桃花
描述
桃花一簇开无主，可爱深红映浅红。
桃花长在桃树上，树的每个节点有一个桃花，调皮的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
C++(clang++11) 解法, 执行用时: 901ms, 内存消耗: 62668K, 提交时间: 2021-01-21 14:35:49
#include<bits/stdc++.h>
using namespace std;
vector<int>p[1000005];
int n,a,b,ans;
void dfs(int q,int f,int s){
if(s>ans){
ans=s;
b=q;
}
for(int it:p[q])
if(it!=f)dfs(it,q,s+1);
}
int main(){
cin>>n;
while(n--){
scanf("%d%d",&a,&b);
p[a].push_back(b);
p[b].push_back(a);
}
dfs(1,0,1);dfs(b,0,1);
cout<<ans<<endl;
}