2023-09-02 11:26:55
发布于：北京
//想看题解，想得美！
全部评论 1
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int MAXN = 100005;int F[MAXN << 1], siz[MAXN], st[MAXN], ed[MAXN], in[MAXN], out[MAXN];
int get(int x) {
if (F[x] != x) F[x] = get(F[x]);
return F[x];
}
void merge(int x, int y) {
x = get(x), y = get(y); if (siz[x] > siz[y]) swap(x, y);
siz[y] += siz[x], F[x] = y;
}int T, N, p[MAXN], ans[MAXN], deg[MAXN];
struct node { int v, next; } E[MAXN << 1]; int head[MAXN], Elen = 1;
void add(int u, int v) { ++Elen, E[Elen].v = v, E[Elen].next = head[u], head[u] = Elen, F[Elen] = Elen, siz[Elen] = 1; }bool ok[MAXN], used[MAXN]; int fa[MAXN], come[MAXN];
void dfs(int u, int ff, int com) {
come[u] = com, fa[u] = ff;
if (!ff) {
for (int i = head[u]; i; i = E[i].next) if (!st[u] && !in[i] && (!ed[u] || get(ed[u]) != get(i) || siz[get(ed[u])] == deg[u]))
dfs(E[i].v, u, i ^ 1);
} else {
if (!ed[u] && !out[com] && (!st[u] || get(st[u]) != get(com) || siz[get(st[u])] == deg[u])) ok[u] = 1;
for (int i = head[u]; i; i = E[i].next) if (E[i].v != ff) {
if (get(i) != get(com) && !in[i] && !out[com] && i != st[u] && com != ed[u]) {
if (get(com) == get(st[u]) && get(i) == get(ed[u]) || get(com) == get(ed[u]) && get(i) == get(st[u])) {
if (siz[get(st[u])] + siz[get(ed[u])] != deg[u]) continue;
}
dfs(E[i].v, u, i ^ 1);
}
}
}
}int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &N); int u, v;
for (int i = 1; i <= N; ++i) scanf("%d", &p[i]);
for (int i = 1; i < N; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u), ++deg[u], ++deg[v];
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) ok[j] = 0;
dfs(p[i], 0, 0);
for (int j = 1; j <= N; ++j) if (j != p[i] && !used[j] && ok[j]) {
ans[i] = j, ed[j] = come[j], used[j] = 1;
int las = come[j] ^ 1;
u = fa[j];
while (u != p[i]) {
merge(come[u], las), ++out[come[u]], ++in[las];
las = come[u] ^ 1, u = fa[u];
}
st[p[i]] = las;
break;
}
}
for (int i = 1; i <= N; ++i) printf("%d ", ans[i]); putchar('\n');
for (int i = 1; i <= N; ++i) head[i] = st[i] = ed[i] = deg[i]2024-12-26 来自 浙江
0
有帮助，赞一个