2026-05-04 19:11:41
发布于：浙江
这是答案
#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
;
}
这里空空如也
有帮助，赞一个