WA#9#10求助
查看原帖
WA#9#10求助
1068809
SpringNeverDie楼主2024/12/15 16:25
#include<bits/stdc++.h>
using namespace std;

vector<int> a[110];
int n,dep[110],dmx,dd[8],ddmx,fath[110];
int v,y,qian,hou;

void dfs(int x,int u,int fa){
	fath[x]=fa;
	dep[x]=u;
	dd[u]++;
	if(a[x].size()==1 && fa!=0){
		dmx=max(dmx,u);	
		return;
	}
	for(int i=0;i<a[x].size();i++){
		if(a[x][i]==fa) continue;
		dfs(a[x][i],u+1,x);
	}
}

void LCA(int a,int b){
	while(dep[a]!=dep[b]){
		if(dep[a]>dep[b]){
			qian++;
			a=fath[a];
			if(a==b){
				break;
			}
		}else{
			hou++;
			b=fath[b];
			if(a==b){
				break;
			}
		}
	}
	
	while(a!=b){
		a=fath[a];
		b=fath[b];
		qian++;
		hou++;
	}
	
} 

int main(){
	cin >> n;
	
	for(int i=1;i<n;i++){
		cin >> v >> y;
		a[v].push_back(y);
		a[y].push_back(v);
	}
	
	cin >> v >> y;
	
	dfs(1,1,0);
	
	LCA(v,y);
	
	for(int i=1;i<=dmx;i++) ddmx=max(ddmx,dd[i]);
	
	cout << dmx <<endl;
	cout << ddmx <<endl;
	cout << qian*2+hou <<endl;
}
2024/12/15 16:25
加载中...