记录编号	590885	评测结果	AAWWWWWWWW
题目名称	喵星人集会	最终得分	20
用户昵称	dream	是否通过	未通过
代码语言	C++	运行时间	0.038 s
提交时间	2024-07-12 14:42:34	内存使用	3.35 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int g[N][N],dis[N][N];
int n;
int aaa[N];
int cnt;
int read(){
	char c;
	int sum=0,f=1;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*f;
}
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
}
int main(){
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=0x3f3f3f3f;
		}
	}
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		if(c=='1'){
			aaa[++cnt]=i;
		}
	}
	for(int i=1;i<=n-1;i++){
		int x,y;
		x=read();
		y=read();
		g[x][y]=1;
		g[y][x]=1;
		dis[x][y]=1;
		dis[y][x]=1;
	}
	for(int i=1;i<=n;i++){
		dis[i][i]=0;
	}
	floyd();
	if(cnt==3){
		int res=1000000;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=4;j++){
				for(int k=1;k<=4;k++){
					for(int q=1;q<=4;q++){
						if(j==k||j==q||k==q){
							continue;
						}
						int a,b,c;
						if(j==4){
							a=dis[aaa[1]][i];
						}
						if(k==4){
							b=dis[aaa[2]][i];
						}
						if(q==4){
							c=dis[aaa[3]][i];
						}
						for(int w=1;w<=n;w++){
							for(int e=1;e<=n;e++){
								if(g[i][w]==0||g[i][e]==0){
									continue;
								}
								if(w==e){
									continue;
								}
								if(a==4){
									b=dis[aaa[2]][w];
									c=dis[aaa[3]][e];
								}					
								if(b==4){
									a=dis[aaa[1]][w];
									c=dis[aaa[3]][e];
								}		
								if(c==4){
									a=dis[aaa[1]][w];
									b=dis[aaa[2]][e];
								}
								res=min(res,a+b+c);
							}
						}
					}
				}
			}
		}
		cout<<res;
	}
	else if(cnt==2){
		int res=1000000;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=3;j++){
				for(int k=1;k<=3;k++){
					if(j==k){
						continue;
					}
					int a,b;
					if(j==3){
						a=dis[aaa[1]][i];
					}
					if(k==3){
						b=dis[aaa[2]][i];
					}
					for(int w=1;w<=n;w++){
						if(g[i][w]==0){
							continue;
						}
						if(j==3){
							b=dis[aaa[2]][w];
						}
						if(k==3){
							a=dis[aaa[1]][w];
						}
						res=min(res,a+b);
					}					
				}
			}
		}
		cout<<res;
	}
	else if(cnt==1){
		cout<<0;
	}
	return 0;
}