玄关求调
  • 板块灌水区
  • 楼主lucy2012
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/7/29 23:25
  • 上次更新2024/7/30 13:33:56
查看原帖
玄关求调
1252442
lucy2012楼主2024/7/29 23:25

代码:

#include<bits/stdc++.h>
using namespace std;
int n,vis[110],cnt,maxx,ans[110],dep,a,b;
vector<int> tree[110];
void d(int x){
	cnt++;
	if(cnt>maxx)
	    maxx=cnt;
	for(int i=0;i<tree[x].size();i++){
		if(!vis[tree[x][i]]){
			vis[tree[x][i]]=1;
			d(tree[x][i]);
		}
	}
	cnt--;
	return;
}
void k(int x,int deep){
	if(deep>dep)
	    dep=deep;
	int ct=0;
	for(int i=0;i<tree[x].size();i++){
		if(!vis[tree[x][i]]){
			ct++;
			vis[tree[x][i]]=1;
			k(tree[x][i],deep+1);
		}
	}
	ans[deep]=ct;
	return;
}
void dfs(int x){
	if(x==b){
		cout<<cnt;
		exit(0);
	}
	for(int i=0;i<tree[x].size();i++){
		if(!vis[tree[x][i]]){
			cnt++;
			vis[tree[x][i]]=1;
			dfs(tree[x][i]);
			cnt--;
		}
	}
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	cin>>a>>b;
	vis[1]=1;
	d(1);
	cout<<maxx<<endl;
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	cnt=0;
	maxx=1;
	k(1,1);
	for(int i=1;i<=dep;i++){
		if(ans[i]>maxx)
		    maxx=ans[i];
	}
	cout<<maxx<<endl;
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	cnt=0;
	maxx=1;
	dfs(a);
	return 0;
}
2024/7/29 23:25
加载中...