Description
Solution
瞎扯
- 你管这叫联赛？？？？NOIplus，
CSPSCP Summer Camp Plus妙啊 - 考场上想了两个小时，想出来了链和菊花，但是因为链比较难打，所以只打了菊花。。。没有时间打链了，难受。
- 然而出来之后发现各路集训队dalao都没有调出来？？同年级的也没有几个打菊花的？？不亏。
- 并且这个输入反了过来，除了方便标程以外就是反人类的操作。
- 链的比较复杂，这里就不说了。而菊花的手玩一下会发现最终会变成将n个点连成一个环，顺位移动，用一个链表和并查集维护一波。
正解
- 正解与这个做法有一点相似，但是却需要转换选择这些边的限制。
- 首先肯定是贪心考虑每一个数字最终所在的编号，要使它最小并且不与之前矛盾，并且保证最后有至少一种方案。
- 对于一个点的所有边肯定有一种选择的顺序，考虑从这里下手。
- 那么对于一条路径要把x的数字移到y，在x到y的路径上，x的出边必须第一个选，y的入边必须最后一个选，经过一个z点，入边必须在出边的前一个选。这就是一个链表的模型。
- 因为只要满足这个条件剩下的边可以随便选，所以这就成为了充分必要条件，并且每一个点的所有连边顺序是互相独立的。
- 那么对于每一次贪心，用一个链表+并查集维护一波就好了。
细节
- 思想如果顺着正解的话这题不失为一道NOIP的好题，
为什么众多集训队dalao在怒刚3h后惨痛爆炸呢？这究竟是人性的扭曲还是道德的沦丧？ - 实际上有很多的细节。
- 例如在确定一些相邻的边的顺序之后，开头和结尾就可能已经确定了，这个要实时更新，或者开头结尾确定，中间有一些限制也就可以限制了，并且如果在某个时刻开头和结尾连在了一起，要保证所有的边都已经夹在他们之间了。
- 而且在某个限制要被安排之前，可能已经刚好安排了这个限制。
- 实际上想清楚就没有问题了，但是刚开始忽略了很多地方的以上的判断，所以删删改改调了好久。
- 怒敲3k
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 2005
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
int T,n,i,j,k,x,y,mi,a[maxn],pre[maxn*2],nex[maxn*2];
int em,e[maxn*2],nx[maxn*2],ls[maxn*2],cnt[maxn];
int st[maxn],ed[maxn];
int fa[maxn*2];
int father(int x){return (fa[x]==x)?x:fa[x]=father(fa[x]);}
void read(int &x){
x=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}
void insert(int x,int y){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; fa[em]=em; cnt[x]++;
em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; fa[em]=em; cnt[y]++;
}
void DFS(int x,int p){
if (ed[x]==p||(!ed[x]&&!nex[p]&&(!st[x]||father(p)!=father(st[x])))){
mi=min(mi,x);
}
for(int i=ls[x];i;i=nx[i]) if (father(i)!=father(p)||nex[p]==i){
if ((!pre[i]||pre[i]==p)&&(!nex[p]||nex[p]==i)&&ed[x]!=p&&st[x]!=i){
if (st[x]&&father(st[x])==father(p)&&ed[x]&&father(ed[x])==father(i) && cnt[x]>1)
continue;
DFS(e[i],i^1);
}
}
}
void link(int x,int y){
x=father(x),y=father(y);
if (x!=y) fa[x]=y;
}
void upd(int x){
if (cnt[x]==1){
if (st[x]&&!ed[x]){
int now,nexi,las;
for(int i=ls[x];i;i=nx[i]) if (i!=st[x]&&!pre[i]) nexi=i;
for(now=st[x];nex[now];now=nex[now]);
for(las=nexi;nex[las];las=nex[las]);
nex[now]=nexi,pre[nexi]=now,ed[x]=las;
link(now,nexi);
} else
if (!st[x]&&ed[x]){
int now,nexi,las;
for(int i=ls[x];i;i=nx[i]) if (i!=ed[x]&&!nex[i]) nexi=i;
for(now=ed[x];pre[now];now=pre[now]);
for(las=nexi;pre[las];las=pre[las]);
pre[now]=nexi,nex[nexi]=now,st[x]=las;
link(now,nexi);
} else
if (st[x]&&ed[x]){
int fir,las;
for(int i=ls[x];i;i=nx[i]) if (!pre[i]&&i!=st[x]) las=i;
else if (!nex[i]&&i!=ed[x]) fir=i;
pre[las]=fir,nex[fir]=las;
link(las,fir);
} else cnt[x]++;
cnt[x]--;
} else
if (cnt[x]==0&&(!st[x]||!ed[x])){
int fir,las;
for(int i=ls[x];i;i=nx[i]) {
if (!pre[i]) fir=i;
if (!nex[i]) las=i;
}
st[x]=fir,ed[x]=las;
}
}
int Cover(int x,int p){
if (x==mi) {
ed[x]=p;
upd(x);
return 1;
}
for(int i=ls[x];i;i=nx[i]) if (i!=p){
if (Cover(e[i],i^1)){
if (!p) st[x]=i; else {
nex[p]=i,pre[i]=p,cnt[x]--;
link(i,p);
}
upd(x);
return 1;
}
}
return 0;
}
int main(){
freopen("ceshi.in","r",stdin);
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
read(T);
while (T--){
read(n);
em=1,mem(ls),mem(pre),mem(nex),mem(st),mem(ed),mem(cnt);
for(i=1;i<=n;i++) read(a[i]);
for(i=1;i<n;i++) read(x),read(y),insert(x,y);
for(i=1;i<=n;i++) cnt[i]--;
for(i=1;i<=n;i++){
x=a[i]; mi=n+1;
if (st[x]) DFS(e[st[x]],st[x]^1); else
for(j=ls[x];j;j=nx[j]) if (!pre[j]&&(!ed[x]||father(j)!=father(ed[x])))
DFS(e[j],j^1);
Cover(x,0);
printf("%d ",mi);
}
printf("
");
}
}