帅哥教教妹子/ll/ll/ll

给个hack也可以啊/ll

#include<bits/stdc++.h>
#define sit set<int>::iterator 
#define F(i,a,b) for(int i=a;i<=b;i++)
#define R(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e6+7;
int n,head[N],cnt,b[N],f[N],tot,ans=1,len[N];
multiset<int> s;
struct edge{
	int nxt,to;
	edge(int _nxt=0,int _to=0){
		nxt=_nxt,to=_to;
	}
}e[N];
bool thy;
inline void add_edge(int from,int to){
	e[++cnt]=edge(head[from],to);
	head[from]=cnt;
}
inline void dfs(int now,int fa){
	int ch=0;
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].to==fa) continue;
		dfs(e[i].to,now);
		ch++;
		f[now]+=f[e[i].to];
	}
	if(ch%2==1){
		for(int i=head[now];i;i=e[i].nxt){
			if(e[i].to==fa) continue;
			len[now]=min(len[now],len[e[i].to]+1);
		}
		ans=max(ans,len[now]);
	}
	else len[now]=0;
	b[now]=ch%2;
	tot=0;
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].to==fa) continue;
	}
	f[now]+=ch/2;
}
inline void dfs2(int now,int fa,int val){
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].to==fa) continue;
		dfs2(e[i].to,now,val);
	}
	tot=0;
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].to==fa) continue;
		s.insert(len[e[i].to]);
		tot++;
	}
//	if(val==2) cout<<"now:"<<now<<"\n";
	int kik=0;
	while(s.size()){
		int val1=*(--s.end());
		if(s.size()==1){
			kik++;
			len[now]=val1+1;
			break;
		}
//		if(val==2)
//			for(auto i:s){
//				cout<<i<<" ";
//			}
//		if(val==2) cout<<"\n";
		s.erase((--s.end()));
		sit val2i=s.upper_bound(val-val1-2);
		if(val2i==s.end()){
			if(*(--s.end())+val1+2<=val){
//				cout<<"1"<<val1<<"\n";
				s.erase(--s.end());
			}
			else{
				kik++;
//				cout<<"2"<<val1<<"\n";
				len[now]=val1+1;
			}
		}
		else{
			int val2=*val2i;
//			cout<<"3"<<val1<<"\n";
			if(--val2i!=s.begin()){
				s.erase(--val2i);
			}
			else{
				kik++;
				len[now]=val1+1;
			}
		}
	} 
//	cout<<kik<<" "<<len[now]<<"\n";
	if(kik>2||(kik==2&&now==1)||(kik==2&&b[now]==1)){
		thy=false;
	}
	s.clear();
	if(len[now]>val) thy=false;
}
int main(){
	cin>>n;
	F(i,1,n-1){
		int from,to;
		cin>>from>>to;
		add_edge(from,to);
		add_edge(to,from);
	}
	dfs(1,0);
	int l=0,r=n,ans;
	while(l<=r){
		int mid=(l+r)>>1;
		F(i,1,n) len[i]=0;
//		cout<<mid<<"\n";
		thy=true;
		dfs2(1,0,mid);
		if(thy) r=mid-1,ans=mid;
		else l=mid+1;
	}
//	cout<<"KINGKINGKING!!!!!!!!!!!!!!!\n";
//	thy=true;
//	puts("");
//	dfs2(1,0,2);
//	F(i,1,n){
//		cout<<len[i]<<" ";
//	}
//	cout<<"\n";
//	cout<<thy<<" THY\n";
	cout<<f[1]+b[1]<<" "<<ans<<"\n";
	return 0;
}