题解（A41.树上的数）

C++版：
// Code by KSkun, 2019/11
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <utility>

typedef long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
static char buf[100000], * p1 = buf, * p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}

inline LL readint() {
LL res = 0, neg = 1; char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}

inline char readsingle() {
char c;
while(!isgraph(c = fgc())) {}
return c;
}

const int MAXN = 2005;

int T, n, ptn[MAXN], deg[MAXN], beg[MAXN], end[MAXN]; // 每个点的第一条/最后一条被删的边
std::vector<int> gra[MAXN];

struct UnionFindSet {
int fa[MAXN];
bool pre[MAXN], nxt[MAXN]; // 一条边有无前后关系
void clear() {
for (int i = 1; i <= n; i++) fa[i] = i;
memset(pre, 0, sizeof(pre));
memset(nxt, 0, sizeof(nxt));
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void join(int x, int y) {
int fx = find(x), fy = find(y);
fa[fy] = fx;
nxt[x] = pre[y] = true;
}
bool sameset(int x, int y) {
return find(x) == find(y);
}
} ufs[MAXN];

int dfs(int u, int f) {
int mn = n + 1;
// 能作为终点的条件：不是起点；入边可以是最后删边；入边之后无必须删边；入边和最后删边不在一条关系链中（只剩一条链时除外）
if (f != 0 && (end[u] == 0 || end[u] == f) && !ufs[u].nxt[f] &&
!(beg[u] != 0 && deg[u] > 1 && ufs[u].sameset(f, beg[u]))) {
mn = stdmin(mn, u);
}
for (int v : gra[u]) {
if (v == f) continue;
if (f == 0) {
// 不能作为起点之后的点的条件：起点的最后删边不是这条；这条边之前有必须删的边；这条边与最后删边在同一条关系链中，且仍有未加入关系链中的边
if (beg[u] != 0 && beg[u] != v) continue;
if (ufs[u].pre[v]) continue;
if (end[u] != 0 && deg[u] > 1 && ufs[u].sameset(v, end[u])) continue;
mn = stdmin(mn, dfs(v, u));
} else {
// 不能作为中间点的条件：入边是最后删边；出边是最先删边；入边和出边已在同一条关系链中；出边之前有必须删边；入边之后有必须删边；应用出入边关系后让最先删边和最后删边在同一条关系链中，且有其他边未在该关系链中
if (f == end[u] || v == beg[u] || ufs[u].sameset(f, v)) continue;
if (ufs[u].pre[v] || ufs[u].nxt[f]) continue;
if (beg[u] != 0 && end[u] != 0 && deg[u] > 2 &&
ufs[u].sameset(f, beg[u]) && ufs[u].sameset(v, end[u])) continue;
mn = std::min(mn, dfs(v, u));
}
}
return mn;
}

bool dfs2(int u, int f, int& tar) {
if (u == tar) {
end[u] = f; return true;
}
for (int v : gra[u]) {
if (v == f) continue;
if (dfs2(v, u, tar)) {
if (f == 0) {
beg[u] = v;
} else {
ufs[u].join(f, v);
deg[u]--;
}
return true;
}
}
return false;
}

int main() {
T = readint();
while (T--) {
n = readint();

    // init
    memset(beg, 0, sizeof(beg));
    memset(end, 0, sizeof(end));
    memset(deg, 0, sizeof(deg));
    for (int i = 1; i <= n; i++) {
        gra[i].clear();
        ufs[i].clear();
    }
    
    // input
    for (int i = 1; i <= n; i++) ptn[i] = readint();
    for (int i = 1, x, y; i < n; i++) {
        x = readint(); y = readint();
        gra[x].push_back(y);
        gra[y].push_back(x);
        deg[x]++; deg[y]++; // deg 表示一个点的边关系构成的链的数量，初始为度数，之后每加入一个关系就对其减 1
    }

    // process
    for (int i = 1; i <= n; i++) {
        int mn = dfs(ptn[i], 0);
        dfs2(ptn[i], 0, mn);
        printf("%d ", mn);
    }
    putchar('\n');
}
return 0;

}