1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| #include <bits/stdc++.h>
const int N = 2050;
int n, id[N];
struct Graph { int to, nxt; } G[N * 2]; int head[N], tot;
struct Chain { int fir, lst, cnt; bool st[N], ed[N]; int fa[N]; inline void init() { fir = lst = cnt = 0; for (int i = 1; i <= n; ++i) { fa[i] = i; st[i] = ed[i] = 1; } } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } } t[N];
inline void addedge(int x, int y) { G[++tot] = { y, head[x] }; head[x] = tot, ++t[x].cnt; }
int find(int x, int fa) { int ans = n + 1; if (fa && (!t[x].lst t[x].lst == fa) && !(t[x].fir && t[x].cnt > 1 && t[x].find(fa) == t[x].find(t[x].fir)) && t[x].ed[fa]) ans = x; for (int i = head[x]; i; i = G[i].nxt) { if ((i >> 1) != fa) { int y = G[i].to; if (!fa) { if ((!t[x].fir t[x].fir == (i >> 1)) && t[x].st[i >> 1] && !(t[x].lst && t[x].cnt > 1 && t[x].find(i >> 1) == t[x].find(t[x].lst))) ans = std::min(ans, find(y, i >> 1)); } else { if ((!t[x].lst fa != t[x].lst) && (!t[x].fir (i >> 1) != t[x].fir) && t[x].find(fa) != t[x].find(i >> 1) && t[x].st[i >> 1] && t[x].ed[fa] && !(t[x].fir && t[x].lst && t[x].cnt > 2 && t[x].find(fa) == t[x].find(t[x].fir) && t[x].find(i >> 1) == t[x].find(t[x].lst))) ans = std::min(ans, find(y, i >> 1)); } } } return ans; }
int merge(int x, int fa, int to) { if (x == to) { t[x].lst = fa; return 1; } for (int i = head[x]; i; i = G[i].nxt) { if ((i >> 1) != fa) { int y = G[i].to; if (merge(y, i >> 1, to)) { if (!fa) { t[x].fir = i >> 1; } else { t[x].ed[fa] = t[x].st[i >> 1] = 0; --t[x].cnt; t[x].fa[t[x].find(fa)] = t[x].find(i >> 1); } return 1; } } } return 0; }
inline void solve() { std::cin >> n; tot = 1; for (int i = 1; i <= n; ++i) { head[i] = 0; t[i].init(); std::cin >> id[i]; } for (int i = 1, x, y; i < n; ++i) { std::cin >> x >> y; addedge(x, y); addedge(y, x); } if (n == 1) { std::cout << "1\n"; return; } for (int i = 1; i <= n; ++i) { int to = find(id[i], 0); merge(id[i], 0, to); std::cout << to << ' '; } std::cout << '\n'; }
int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int T; std::cin >> T; while (T--) solve(); return 0; }
|