记录编号	595833	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]树上的数	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	6.327 s
提交时间	2024-10-17 20:18:19	内存使用	15.83 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 2010;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

int n;
int d[N],fi[N],en[N],id[N];
vector<int>e[N];


struct DSU{
	int fa[N];
	bool pre[N],nx[N];
	void clear(){for(int i = 1;i <= n;i++)fa[i] = i,pre[i] = nx[i] = 0;} 
	int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x,int y){
		x = find(x),y = find(y);
		if(x == y)return;
		fa[y] = x;
		nx[x] = pre[y] = 1;
	}
	bool is(int x,int y){return find(x) == find(y);}
}U[N];


int ans = 1e8;
void dfs(int x,int fa){
	if(fa != 0 && (en[x] == fa || en[x] == 0) && !U[x].nx[fa]
	&& (d[x] <= 1 || fi[x] == 0 || !U[x].is(fa,fi[x])))ans = min(ans,x);
	//终点 
	for(int y : e[x]){
		if(y == fa)continue;
		if(fa == 0){//起点 
			if((fi[x] == 0 || fi[x] == y) && !U[x].pre[y]
			&& (d[x] <= 1 || en[x] == 0 || !U[x].is(y,en[x])))dfs(y,x);
		}
		else{//中间点 
			if(en[x] != fa && fi[x] != y && !U[x].is(fa,y) && !U[x].nx[fa] && !U[x].pre[y]
			&& (d[x] <= 2 || (fi[x] == 0 || !U[x].is(fi[x],fa)) || (en[x] == 0 || !U[x].is(y,en[x]))))dfs(y,x);
		}
	}
}
bool dfs2(int x,int fa,int v){
	if(x == v)return en[x] = fa,1;
	for(int y : e[x]){
		if(y == fa)continue;
		if(dfs2(y,x,v)){
			if(fa == 0)fi[x] = y;
			else U[x].merge(fa,y),d[x]--;
			return 1;
		}
	}
	return 0;
}

int main(){
	freopen("2019tree.in","r",stdin);
	freopen("2019tree.out","w",stdout);
	int t = read();
	while(t--){
		n = read();
		for(int i = 1;i <= n;i++)d[i] = en[i] = fi[i] = 0,e[i].clear(),U[i].clear();
		for(int i = 1;i <= n;i++)id[i] = read();
		for(int i = 1;i < n;i++){
			int x = read(),y = read();
			e[x].pb(y),e[y].pb(x);
			d[x]++,d[y]++;
		}
		for(int i = 1;i <= n;i++){
			ans = 1e8;
			dfs(id[i],0);
			dfs2(id[i],0,ans);
			printf("%d ",ans);
		}
		printf("\n");
	}

	return 0;

}