这是答案
#include<bits/stdc++.h>
#define cs const
using namespace
std;
int read()
{
int cnt = 0, f = 1; char ch = 0
;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1
; }
while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar
();
return
cnt * f;
}
cs
int N = 2e3 + 5
;
int
T, n, ps[N];
int
L[N][N], R[N][N], fa[N][N];
int
st[N], ed[N];
int
siz[N][N], pre[N];
vector<
int
> v[N];
> bool
> vis[N];
> int
> ans[N];
> int find(int rt, int x){ return fa[rt][x] == x ? x : fa[rt][x] = find
> (rt, fa[rt][x]); }
> void dfs(int u, int f)
> {
> for(int i = 0; i < v[u].size(); i++) if
> (v[u][i]^f) pre[v[u][i]] = u;
> if(f == 0
> ){
> for(int i = 0; i < v[u].size
> (); i++){
> int
> t = v[u][i];
> if(ed[t]) continue; // finish position
> if(L[u][t] != t) continue
> ;
> if(find(t, st[t]) == find
> (t, u)){
> if(siz[t][find(t, st[t])] != v[t].size()) continue
> ;
> }
> if(find(u, ed[u]) == find
> (u, t)){
> if(siz[u][find(u, ed[u])] != v[u].size()) continue
> ;
> }
> if(R[t][u] != u) continue
> ;
> vis[t] =
> 1
> ;
> }
> }
> else
> {
> for(int i = 0; i < v[u].size
> (); i++){
> int
> t = v[u][i];
> if(t == f) continue
> ;
> if(ed[t]) continue
> ;
> if((R[u][f] == t && L[u][t] == f) || (R[u][f] == f && L[u][t] == t && find(u, f) != find
> (u, t))){
> if(find(t, st[t]) == find
> (t, u)){
> if(siz[t][find(t, st[t])] != v[t].size()) continue
> ;
> }
> if(find(u, t) == find
> (u, ed[u])){
> if(find(u, f) == find
> (u, st[u])){
> if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue
> ;
> }
> }
> if(find(u, t) == find
> (u, st[u])){
> if(find(u, f) == find
> (u, ed[u])){
> if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue
> ;
> }
> }
> if(R[t][u] == u) vis[t] = 1
> ;
> }
> }
> }
> if(f == 0
> ){
> for(int i = 0; i < v[u].size
> (); i++){
> int
> t = v[u][i];
> if(find(u, t) == find
> (u, ed[u])){
> if(siz[u][find(u, ed[u])] != v[u].size()) continue
> ;
> }
> dfs
> (t, u);
> }
> }
> else
> {
> if
> (ed[u] != f){
> for(int i = 0; i < v[u].size
> (); i++){
> int
> t = v[u][i];
> if(t == f) continue
> ;
> if( ((R[u][f] == f && find(u, f) != find
> (u, t)) || R[u][f] == t) &&
> ((L[u][t] == t &&
> find(u, t) != find
> (u, f)) || L[u][t] == f) ){
> if(find(u, t) == find
> (u, ed[u])){
> if(find(u, f) == find
> (u, st[u])){
> if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue
> ;
> }
> }
> if(find(u, t) == find
> (u, st[u])){
> if(find(u, f) == find
> (u, ed[u])){
> if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue
> ;
> }
> }
> dfs
> (t, u);
> }
> }
> }
> }
> }
> void modify(int u, int v){ // u -> v
> ed[v] = pre[v];
> R[v][pre[v]] =
> -1
> ;
> int
> nxt = v; v = pre[v];
> while
> (v ^ u){
> R[v][pre[v]] = nxt;
> L[v][nxt] = pre[v];
> int fx = find
> (v, pre[v]);
> int fy = find
> (v, nxt);
> if
> (fx ^ fy){ fa[v][fy] = fx; siz[v][fx] += siz[v][fy]; }
> nxt = v; v = pre[v];
> } st[v] = nxt; L[v][nxt] =
> -1
> ;
> }
> void Solve()
> {
> n =
> read
> ();
> for(int i = 1; i <= n; i++) ps[i] = read
> ();
> for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) fa[i][j] = L[i][j] = R[i][j] = j, siz[i][j] = 1
> ;
> for(int i = 1; i <= n; i++) v[i].clear(), st[i] = ed[i] = 0
> ;
> for(int i = 1
> ; i < n; i++){
> int x = read(), y = read
> ();
> v[x].
> push_back
> (y);
> v[y].
> push_back
> (x);
> }
> for(int t = 1
> ; t <= n; t++){
> int
> nx = ps[t];
> for(int i = 1; i <= n; i++) vis[i] = pre[i] = 0
> ;
> dfs(nx, 0
> );
> for(int i = 1
> ; i <= n; i++){
> if(vis[i]){ ans[t] = i; modify(nx, i); break
> ; }
> }
> }
> for(int i = 1; i <= n; i++) cout << ans[i] << " "
> ;
> puts(""
> );
> }
> int main()
> {
> T =
> read
> ();
> while(T--) Solve
> ();
> return 0
> ;
> }
