算法1 (贪心+树形DP) O(n)O(n)O(n) 贪心思路： 我们要让前面的数尽量小，那么我们从1开始找，找到第一个出现1的节点n，说明我们要把1交换到n上。 一次交换能够影响到的范围肯定是与节点n相连的所有节点（以后简称影响区域）。 我们发现一个规律，当i < 1，intervals(i) = intervals(i - 1)，因为加入最新的数，数的范围不会变。当 i > 1，intervals(i) = intervals(i - 1) - 1 因为加上一个数字，数字的种类+1，影响区域就会减少1。 比如： 初始的intervals(1) = 1，表示整个序列都只有数字1，只能交换数字1，交换完后整个区域都有了数字1到t，intervals(2) = t - 1，表示这个时候，可以交换数字2了，交换完后，这个区域范围变成了1到t，数字1修改后又变成了2，数量变为0，影响区域就缩小了1。以此类推。 这样看下来，我们貌似可以根据交换序列从后往前遍历，然后根据交换序列进行更新即可。 由于更新的时候要在区间上进行DP，在树上，我们需要借用从叶子节点到根节点dfs的过程，先从叶子节点开始更新，因为根节点是整个区间的父区间，所以要从叶子节点计算出的区间来计算父区间。具体DP，我们在区间左边的影响区域我们可以通过左子树来更新，右边的区域通过右子树来更新。

//想看题解，想得美！

所有人代码几乎一模一样

递归报错

//想看题解，想得美！

#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] = used[i] = ans[i] = 0; for (int i = 1; i <= Elen; ++i) in[i] = out[i] = 0; Elen = 1; } return 0; }