前言
被队友（大爹）易giegie要求做这道题，一天一夜绞尽脑汁终于写出来了。（下了样例test1调试）
然后被要求写博客
虽然我觉得没啥用，但是写一下吧
一些说明
1.把数在删边时交换的过程看做移动，停留过的点和相关的边认为是经过这些点和边
2.把一条边看做两条有向边，数在交换时的移动有方向，经过的边用与移动同向的有向边代表，那么数经过的点和有向边，就称为路径
3.每条边一定被删一次，也只能被删一次
性质
1.一个数不会经过一个点两次(离开一个点就再也不会回来)
证明：如果一个数经过一个点两次，那么他经过的边会形成一个环，然而树没有环
2.一个数不会留在原来所在的点
证明：一个点总有连边，这个点上的数总会被交换出去，一旦离开就再也回不来了（性质1）
3.从一个点到达另一个点只有一条路径
树上显然
思考流程
字典序最小最先考虑贪心，数字小的编号一定要尽量小。
由性质3可知只要考虑可不可行，不用考虑怎样到达，因为交换到目标点的路径唯一。
没其他思路，先模拟贪心过程。
说明：以下思路不考虑一些说明中的第三条中的至少删一次
首先从数字1开始，一开始树没有任何操作，1哪里都可以去。如果
- 所在点编号为1，由性质2可知到不了1，那么走到2，留下一条路径，记下来。
- 所在点编号不为1，那么就走到1，留下一条路径，记下来。
再从2开始，此时树上已经留下了一条路径。找到除了2所在点和1选择的点之外，2能选择的最小点，走到这个点又会产生一条路径，思考两条路径可能的关系
说明：这里路径的边当做无向边考虑
两条路径可能存在的关系
1.经过的点和边都没有重复
2.有一段边重复
3.某路径的起点或终点在另一条路径上，边没有重复
没有第四种
首先显然边重复两个端点也重复，边重复一定点重复
断言：如果边有重复，只有一段会重复，不可能多段重复
证明：如果多段重复，那么取两段，两条路径使从一段到另一段有两条路径可走，形成了环，而树上无环，矛盾
断言：如果边无重复，点有重复，只有一个点会重复
证明：如果有多个点重复，取两个点，同上，两条路径成环，矛盾
回到原来的模拟流程
- 点和边都没有重复，这条路径可行，爽爽记录下来。
- 点重复，边没有重复，不知道可不可行，待会再说，先记录下来
- 边重复。
- 同向重复，一条有向边只能被经过一次，因为一点边只会被删去一次，矛盾，路径无效
- 反向重复。（见下方的发现）
- 反向边重复只有一条边。由于边的时间顺序是两条边的关系，只重复一条边也就是只重复一个点，两个DAG重复了一个点仍然是DAG，显然吧。可行就记录下来。
- 反向边重复超过一条边。那么取相邻两条边，记为a,b。如果第一条路径中a,b顺序为a->b,那么另一条路径就是b->a，这两条边就成环了，无效路径。
发现了一个神奇的事情。一个数到达另一个点所经过的路径，其实是有时间顺序的，也就是按照路径从头走到尾，如果中间有一条边被删了而数还没走到端点，就没有参与交换，那就完了
所以，一条路径从头到尾时间也是有序的。
可以把边也看成点，时间关系当作边，形成一张图，如果无环说明可行
综上考虑，我们发现路径最多有以下的关系：完全不重复，一个点重复，边反向一条重复。
再考虑边重复，重复的边两个方向都走过了，可以认为这条边已经断了。树被分成了森林。然后惊奇的发现，两条路径在两个树中仍然可以看做是两条路径，而且无重复
所以路径之间可等效的看为只有完全不重复或者重复一个点的关系。
回到模拟流程。当我们从3，或者更大的数开始模拟时，我们面对的就是一堆满足上述关系的路径，然后我们夹缝中求生存，找到能到达的最大点，一直到结束即可。
复杂度分析
枚举每一个数o(n)，枚举每一个点o(n)，每一个点dfs找路径o(n)，判断路径是否合理o(1)。n^3爆炸
不过可以dfs过程中走到一个点判断一个点，那么平方复杂度可接受。代码开打
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
typedef int LL;
#define pii std::pair<LL,LL>
#define MK(a,b) std::make_pair(a,b)
#define mid (l+r>>1)
const LL maxn=(LL)1e5+5;
inline LL read(){
char ch=getchar();bool f=0;int x=0;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
if(f) x=-x;return x;
}
struct Edge{
int to,nxt,belong;
}edge[maxn<<1];
LL head[maxn],ecnt;
void adde(int u,int v,int belong=0){
edge[++ecnt]=(Edge){v,head[u],belong};
head[u]=ecnt;
}
LL n,m,k;
bool used[maxn];
LL fa[maxn];
int find(LL x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void link(LL u,LL v){
u=find(u),v=find(v);
fa[v]=u;
}
void init(int n){
memset(head,0,sizeof(LL)*(n+5));
memset(used,0,sizeof(bool)*(n+5));
for(LL i=0;i<=n;i++) fa[i]=i;
ecnt=1;
}
LL pos[maxn],ar[maxn];
LL fin,lst;
LL stk[maxn],top,ans[maxn];
void dfs1(int u,int Fr,int pos){
LL llst=lst;
for(LL i=head[u];i;i=edge[i].nxt){
if(edge[i].belong==-1) continue;
LL v=edge[i].to,bl=find(edge[i].belong);
if(bl==-1||lst==bl||(i^1)==Fr) continue;//
if(edge[i].belong>0) lst=bl;
dfs1(v,i,pos);
}
if(u<fin&&u!=pos&&!used[u])
fin=u;
lst=llst;
}
bool dfs2(LL u,LL Fa){
if(u==fin) return 1;
for(LL i=head[u];i;i=edge[i].nxt){
LL v=edge[i].to;
if(v==Fa) continue;
stk[++top]=i;
if(dfs2(v,u)) return 1;
top--;
}
return 0;
}
void dfs3(LL i){
while(top){
int e=stk[top];
if(edge[e].belong){
link(i,edge[e].belong);
edge[e].belong=-1;
}
else{
edge[e].belong=-1;
edge[e^1].belong=i;
}
top--;
}
}
signed main(){
LL T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) pos[i]=read(),ar[pos[i]]=i;
init(n);
int u,v;
for(LL i=1;i<n;i++){
u=read();v=read();
adde(u,v);adde(v,u);
}
for(LL i=1;i<=n;i++){
fin=n+1;lst=-1;
dfs1(pos[i],0,pos[i]);
top=0;dfs2(pos[i],0);
dfs3(i);used[fin]=1;
ans[i]=fin;
}
for(LL i=1;i<=n;i++) printf("%lld ",ans[i]);putchar('\n');
}
}
打完测样例就会发现有些点答案是n+1，也就是没找到点。这是什么原因？
调试一下发现是某些点只能到剩自己原来的点没有被占用，然而不能留在自己的点，所以错了。
直接原因是我没有模仿真正的删边，而是固定一条路径，为了固定路径会使某些点无路可走。
根本原因是没能保证每条边都被删一次
懒得说中间惨痛但无效且错误的改良思路了
直接最后的思路
最后的思路
论证的时候认为边重复被等效掉了，但是代码实现有反向单边重复
当我们想固定一条路径的时候，我们要求相邻两条边一定要紧挨着发生，公共点在这两个交换中间不能参与其他交换，否则数就跑走了。
起点的起边一定比起点的其他边要早，不然数在起点就被先换走了，同时由于性质1再也不会回到这个点
终点的终边一定比终点得其他边要晚，不然数到达终点又被换走了。
会发现这些时间关系都是围绕着一个点展开的，也就是我们要做到局部有序。
除了局部之间的时间限制，边之间的时间限制链就和路径链一样，可以通过路径传递，起点和终点的之间限制都是围绕点的限制，但通过路径间的点重复也可以被传递，也就是通过不同路径间的点交传递
断言：局部有序可以推出整体有序
证明：如果局部有序而整体无序，那么局部之间只能靠路径来提供时间顺序限制，无序即时间成环，如果时间链成环，路径也成环，然而树上路径不成环，所以断言的否定是错的，断言成立
实现方法
三遍dfs，dfs1找可行到达的点最小的点，dfs2已知终点找路径，dfs3把关系加进去
判可行就是判是否时间局部有序。局部有序要求起点局部有序，终点局部有序，中间点局部有序
每一条有向边归属于起点，双向链表建立相邻关系，sst，eed数组记录起点终点，用并查集把相邻的点合并到一个集合，通过集合数和指向关系等判断是否有序
详见代码
说一下三种有序吧。
三种有序指的是加入路径要求的某种关系后仍然有序
- 起点有序
- 已有起点，不能再设置起点。或者待设置的起点是某一条边的后面一条边。返回 false
- 没有起点，有终点，待设置起点和终点在一个集合里，说明操作从起点到终点没有间隙，如果这是唯一的集合，返回 true，否则另一个集合没法在起点终点之间被完成删边，返回 false，也就是返回 siz==1
- 没啥问题，返回 true
- 终点有序同理
- 中间点有序
记要加入的关系为fr->to- 如果fr已经有指向或者to已经被指向，不能再加入关系 返回false
说明：哪怕fr已经指向的是to也不行，因为路径不能重复两条边 - fr和终点在一个集合或者to和起点在一个集合里，无法指/被指 ，返回false
- fr和起点在一个集合，to和终点在一个集合，返回 siz==2
- 没啥问题，返回 true
- 如果fr已经有指向或者to已经被指向，不能再加入关系 返回false
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
typedef int LL;
#define pii std::pair<LL,LL>
#define MK(a,b) std::make_pair(a,b)
#define mid (l+r>>1)
const LL maxn=(LL)5005;
inline LL read(){
char ch=getchar();bool f=0;int x=0;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
if(f) x=-x;return x;
}
struct Edge{
int to,nxt;
}edge[maxn<<1];
LL head[maxn],ecnt,siz[maxn];
void adde(int u,int v){
edge[++ecnt]=(Edge){v,head[u]};
head[u]=ecnt;siz[u]++;
}
int sst[maxn],eed[maxn];
LL n,m,k;
bool used[maxn];
LL fa[maxn<<1];
int find(LL x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void link(int u,int v){
u=find(u),v=find(v);
fa[v]=u;
}
LL pre[maxn<<1],nxt[maxn<<1];
bool goodend(int u,int to){
if(eed[u]||nxt[to]) return 0;
if(find(to)==find(sst[u])) return (siz[u]==1);
return 1;
}
bool badst(int u,int Fr){
if(sst[u]||pre[Fr]) return 1;
if(find(Fr)==find(eed[u])) return (siz[u]^1);
return 0;
}
bool badmid(int u,int Fr,int to){
if(nxt[Fr]||pre[to]||find(Fr)==find(to)) return 1;
if(find(Fr)==find(eed[u])||find(to)==find(sst[u])) return 1;
//if(Fr==eed[u]||to==sst[u]) return 1;
if(find(Fr)==find(sst[u])&&find(to)==find(eed[u])) return (siz[u]^2);
return 0;
}
void init(int n){
memset(head,0,sizeof(LL)*(n+5));
memset(siz,0,sizeof(LL)*(n+5));
memset(sst,0,sizeof(LL)*(n+5));
memset(eed,0,sizeof(LL)*(n+5));
memset(pre,0,sizeof(LL)*(2*n+5));
memset(nxt,0,sizeof(LL)*(2*n+5));
memset(used,0,sizeof(bool)*(n+5));
for(LL i=0;i<=n*2;i++) fa[i]=i;
ecnt=1;//ecnt2=1;
}
LL pos[maxn],ar[maxn];
LL fin,lst;
LL stk[maxn],top,ans[maxn];
void dfs1(int u,int Fr,int pos){
for(LL i=head[u];i;i=edge[i].nxt){
LL v=edge[i].to;
if((i^1)==Fr) continue;//
if((u==pos&&badst(pos,i)||(u!=pos&&badmid(u,Fr^1,i)))) continue;
dfs1(v,i,pos);
}
if(u<fin&&u!=pos&&!used[u]&&goodend(u,Fr^1))
fin=u;
}
bool dfs2(LL u,LL Fa){
if(u==fin) return 1;
for(LL i=head[u];i;i=edge[i].nxt){
LL v=edge[i].to;
if(v==Fa) continue;
stk[++top]=i;
if(dfs2(v,u)) return 1;
top--;
}
return 0;
}
void dfs3(LL i){
sst[pos[i]]=stk[1];
eed[fin]=stk[top]^1;
while(--top){
nxt[stk[top]^1]=stk[top+1];
pre[stk[top+1]]=stk[top]^1;
link(stk[top]^1,stk[top+1]);
siz[edge[stk[top]].to]--;
}
}
signed main(){
freopen("data.in","r",stdin);
LL T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) pos[i]=read(),ar[pos[i]]=i;
init(n);
int u,v;
for(LL i=1;i<n;i++){
u=read();v=read();
adde(u,v);adde(v,u);
}
for(LL i=1;i<=n;i++){
fin=n+1;lst=-1;
dfs1(pos[i],0,pos[i]);
top=0;dfs2(pos[i],0);
dfs3(i);used[fin]=1;
ans[i]=fin;
}
for(LL i=1;i<=n;i++) printf("%lld ",ans[i]);putchar('\n');
}
}