求助 80pts WA#8#9
查看原帖
求助 80pts WA#8#9
457208
telesport楼主2021/9/3 19:46
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int head[105],cnt=0,ll[105][25],depth[105],nex[105*2],to[105*2],from[105*2],maxdep=0,maxwid=0,wid[105];
void build(int x,int y){
	from[++cnt]=x;
	to[cnt]=y;
	nex[cnt]=head[x];
	head[x]=cnt;
}
void lca(int x,int y){
	int i;
	depth[x]=depth[y]+1;
	wid[depth[x]]++;
	maxdep=max(maxdep,depth[x]);
	ll[x][0]=y;
	for(i=1;i<=21;i++){
		ll[x][i]=ll[ll[x][i-1]][i-1];
	} 
	for(i=head[x];i!=-1;i=nex[i]){
		if(to[i]!=y){
			lca(to[i],x);
		}
	}
	return;
} 
int find(int x,int y){
	int i,xx=x,yy=y,roadx=0,roady=0;
	if(depth[x]<depth[y]) swap(x,y);
	for(i=20;i>=0;i--){
		if(depth[ll[x][i]]>depth[y]) x=ll[x][i];
	}
	if(x==y) return x;
	for(i=20;i>=0;i--){
		if(ll[x][i]!=ll[y][i]){
			x=ll[x][i];
			y=ll[y][i]; 
		}
	}
	return ll[x][0];
}
int main(){
	int i,j,m,n,k,x,y,s;
	cin>>n; 
	for(i=1;i<=n;i++) head[i]=-1;
	for(i=1;i<=n-1;i++){
		scanf("%d%d",&x,&y);
		build(x,y);
		build(y,x);
	}
	scanf("%d%d",&x,&y);
	s=1;
	lca(s,1); 
	for(i=1;i<=maxdep;i++) maxwid=max(maxwid,wid[i]);
	cout<<maxdep<<endl<<maxwid<<endl<<2*(depth[x]-depth[find(x,y)])+depth[y]-depth[find(x,y)];
	return 0;
} 
2021/9/3 19:46
加载中...