Solution
以下是各位大佬们总结出来的正确的考场拿分顺序。
10pts 暴力
（这不就是我在考场上写的吗 QWQ
暴搜枚举删边顺序，复杂度 (O(n!))
Code
附上考场代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 433333;
int n, k, T, w[N], ans[N], e[N], f[N], vis[N], tre[N];
bool lit()
{
for(int i = 1; i <= n; i++)
if(w[i] != ans[i]) return w[i] < ans[i];
return false;
}
void dfs(int cnt)
{
if(cnt == n - 1)
{
if(lit())
for(int i = 1; i <= n; i++) ans[i] = w[i];
return ;
}
for(int i = 1; i < n; i++)
{
if(vis[i]) continue;
swap(w[tre[e[i]]], w[tre[f[i]]]);
swap(tre[e[i]], tre[f[i]]);
vis[i] = 1;
dfs(cnt + 1);
vis[i] = 0;
swap(w[tre[e[i]]], w[tre[f[i]]]);
swap(tre[e[i]], tre[f[i]]);
}
}
int main()
{
//freopen("tree.in", "r", stdin);
//freopen("tree.out", "w", stdout);
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
memset(ans, 0x3f, sizeof(ans));
memset(w, 0, sizeof(w));
memset(tre, 0, sizeof(tre));
memset(e, 0, sizeof(e));
memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
for(int i = 1; i <= n; i++) tre[w[i]] = i;
for(int i = 1; i < n; i++)
scanf("%d%d", &e[i], &f[i]);
dfs(0);
for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
printf("
");
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
35pts 菊花图
假设交换顺序是 {(p_{rt}, p_1, p_2, p_3...p_{n-1})}，经过手模可以发现，最后每个点的权值都跑到下一个点的位置上去了。就是 (a_{rt}) -> (p_1) , (a_{p_1}) -> (p_2) , (a_{p_2}) -> (p_3...a_{p_{n-1}}) -> (p_{rt})。
于是我们得出一个性质：对于每个点，让它与它最后的位置连边，最后会形成一个大环。既然是一个大环，那么中间形成小环的情况就不合法。因此只需要贪心地连边，用并查集维护。
Code
代码仅是菊花图。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2333333;
int T, rt, n, p[N], a[N], du[N], fa[N], vis[N], ans[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
memset(fa, 0, sizeof(fa));
memset(du, 0, sizeof(du));
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
for(int i = 1; i <= n; i++) scanf("%d", &p[i]), a[p[i]] = i;
for(int u, v, i = 1; i < n; i++) scanf("%d%d", &u, &v), du[u]++, du[v]++;
for(int i = 1; i <= n; i++) fa[i] = i; //并查集初始化
for(int i = 1; i <= n; i++) if(du[i] > 1) rt = a[i]; //找到菊花图的根节点
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(!vis[j] && find(p[i]) != find(j)) //找当前权值能到的最小的点
{
fa[find(p[i])] = find(j);
ans[i] = j, vis[j] = 1;
break;
}
for(int i = 1; i < n; i++) printf("%d ", ans[i]);
for(int i = 1; i <= n; i++) if(!vis[i]) printf("%d
", i);
}
return 0;
}
60pts 链
（开局一张图，内容全靠编）
假设图中的 (a_u) 要向右跑到图中的 (v) 点去，我们可以得到以下几条性质：
(1.) (u) 点的右边要在左边删之前删，要不然 (u) 点早就跑到左边了。
(2.) (u) 和 (v) 之间的点都是先删左边再删右边
(2.) (v) 点右边的边要在左边的边删之前删，要不然好不容易跑到 (v) 点的 (a_u) 一会儿就会继续向右跑
同样的道理，(a_v) 向左跑到 (u) 也可以轻松地推出来。
抽象一下这个东西：给每个点打一个 tag，tag = 0 表示未标记；tag = 1 表示先删左边再删右边；tag = 2 表示先删右边再删左边。
每次只要贪心地去找，让较小的权值尽量到达编号较小的点。删边过程中添加的标记不能与已有的标记冲突。
注意： 链开头的点和结尾的点没有标记。
Code
代码仅是链。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6666;
struct edge { int nxt, to; } e[N];
int T, n, st, tot, cnt, l[N], p[N], a[N], du[N], vis[N];
int ans[N], tag[N], use[N], head[N];
void add(int x, int y)
{
e[++cnt] = (edge) { head[x], y };
head[x] = cnt;
}
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
tot = cnt = st = 0;
memset(p, 0, sizeof(p));
memset(l, 0, sizeof(l));
memset(du, 0, sizeof(du));
memset(use, 0, sizeof(use));
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
memset(head, 0, sizeof(head));
for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
for(int u, v, i = 1; i < n; i++)
{
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
du[u]++, du[v]++;
}
for(int i = 1; i <= n; i++) if(du[i] == 1) { st = i; break; }
// 找到这条链
while(st)
{
int fl = 0;
l[++tot] = st, vis[st] = 1, use[st] = tot;
for(int i = head[st]; i; i = e[i].nxt)
{
int v = e[i].to;
if(!vis[v])
{
st = v, fl = 1;
break;
}
}
if(fl == 0) break;
}
// 开始贪心统计答案
memset(tag, 0, sizeof(tag));
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++)
{
int res = 0x3f3f3f3f, ki = 0;
// 往右边走
if(!tag[p[i]] || tag[p[i]] == 2)
{
for(int j = use[p[i]] + 1; j <= n; j++)
{
if(!tag[l[j - 1]] || tag[l[j - 1]] == 1 || l[j - 1] == p[i])
{
if((!tag[l[j]] || tag[l[j]] == 2) && !vis[l[j]])
if(res > l[j]) res = l[j], ki = 1;
}
else break;
}
}
// 往左边走
if(!tag[p[i]] || tag[p[i]] == 1)
{
for(int j = use[p[i]] - 1; j >= 1; j--)
{
if(!tag[l[j + 1]] || tag[l[j + 1]] == 2 || l[j + 1] == p[i])
{
if((!tag[l[j]] || tag[l[j]] == 1) && !vis[l[j]])
if(res > l[j]) res = l[j], ki = 2;
}
else break;
}
}
// 如果往右边走更优
if(ki == 1)
{
tag[p[i]] = 2, tag[res] = 2;
for(int j = use[p[i]] + 1; l[j] != res; j++) tag[l[j]] = 1;
}
// 如果往左边走更优
if(ki == 2)
{
tag[p[i]] = 1, tag[res] = 1;
for(int j = use[p[i]] - 1; l[j] != res; j--) tag[l[j]] = 2;
}
tag[l[1]] = tag[l[n]] = 0, ans[i] = res;
vis[res] = 1;
}
for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
printf("
");
}
return 0;
}
100pts 正解
不会