Submission #1356213

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n,a,b,cnt,dist[110000];vector<int>x[110000];bool used[110000];
void dfs(int pos,int depth){
	if(used[pos]==true)return;
	used[pos]=true;dist[pos]=depth;
	for(int i=0;i<x[pos].size();i++)dfs(x[pos][i],depth+(x[pos].size()==2));
}
int main(){
	cin>>n;for(int i=1;i<=n-1;i++){cin>>a>>b;x[a].push_back(b);x[b].push_back(a);}
	for(int i=1;i<=n;i++){if(x[i].size()==1)cnt++;}
	for(int i=1;i<=n;i++)used[i]=false;dfs(1,0);
	int maxn=0,maxid=0;for(int i=1;i<=n;i++){if(maxn<dist[i]){maxn=dist[i];maxid=i;}}
	for(int i=1;i<=n;i++)used[i]=false;dfs(maxid,0);
	sort(dist+1,dist+n+1);
	cout<<cnt+dist[n]<<endl;
	return 0;
}

Submission Info

Judge Result