本文共 3645 字，大约阅读时间需要 12 分钟。

题目

思路

假设数字$1$可以移动到$1$号点（即：存在合法的移动方式），那么我们就要 不惜一切代价 把$1$移动过去再说。

这告诉我们，难点是判断是否存在合法的方案——不与已有的移动要求冲突。

对于每个点，其邻边的删除顺序是独立的。发现一次移动等价于：

• 对于起点，路径上的边必须第一个被删掉；
• 对于中转点，路径上的入边与出边相继被删掉；
• 对于终点，路径上的边必须最后被删掉。

然后用链表暴力判断即可。唯一不容易想到的一点，就是 过早封闭——$a$必须第$x$个被删掉，$b$必须倒数第$y$个被删掉，如果 $x+y\ne d_x$（$d_x$表示$x$的度），那么也不能连接。

其他情况自己推一下就好了。也可以看代码。

代码

#include <cstdio>#include <iostream>#include <vector>using namespace std;inline int readint(){   	int a = 0, f = 1; char c = getchar();	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -1;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}struct Edge{   	int to, nxt;	Edge(){    }	Edge(int T,int N):to(T),nxt(N){    }};const int MaxN = 2000;int n, head[MaxN+1], cntEdge;Edge edge[MaxN<<1];int located[MaxN+1], degree[MaxN+1];void addEdge(int from,int to){   	edge[cntEdge] = Edge(to,head[from]);	head[from] = cntEdge ++;	++ degree[from];}void input(){   	n = readint(); cntEdge = 0;	for(int i=1; i<=n; ++i)		head[i] = -1, degree[i] = 0;	for(int i=1; i<=n; ++i)		located[i] = readint();	for(int i=1,x,y; i<n; ++i){   		x = readint(), y = readint();		addEdge(x,y), addEdge(y,x);	}}struct Node{   	Node *pre, *suf;	int preLen, sufLen, id;	void dispose(){   		pre = suf = nullptr; // C++11对于(void*)0的新写法 		preLen = sufLen = (MaxN<<2);	}}node[MaxN<<1], *Head[MaxN+1], *tail[MaxN+1];bool beTail(Node *o,int pos){    // 能否成为最后一条 	if(tail[pos] != nullptr) return false;	if(o->suf != nullptr) return false;	if(o->preLen < degree[pos])		return false;	return true;}bool beHead(Node *o,int pos){    // 能否成为第一条 	if(Head[pos] != nullptr) return false;	if(o->pre != nullptr) return false;	if(o->sufLen < degree[pos])		return false;	return true;}bool linkNode(Node *a,Node *b,int pos){   	if(a->suf == b) return true;	if(a->suf != nullptr or b->pre != nullptr)		return false;	if(tail[pos] == a or Head[pos] == b)		return false;	if(a->preLen+b->sufLen < degree[pos])		return false; // 过早封闭 	if(a->id == b->id)		return false; // 已经在一条链中了 	return true;}void linkNode(Node *a,Node *b){   	a->suf = b, b->pre = a;	for(Node *o=b; o!=nullptr; o=o->suf){   		o->preLen = o->pre->preLen+1;		o->id = o->pre->id;	}	for(Node *o=a; o!=nullptr; o=o->pre)		o->sufLen = o->suf->sufLen+1;}void toBeHead(Node *o,int pos){   	Head[pos] = o; o->preLen = 1;	for(o=o->suf; o!=nullptr; o=o->suf)		o->preLen = o->pre->preLen+1;}void toBeTail(Node *o,int pos){   	tail[pos] = o; o->sufLen = 1;	for(o=o->pre; o!=nullptr; o=o->pre)		o->sufLen = o->suf->sufLen+1;}int answer;void dfs(int x,int pre){   	pre ^= 1;	if(beTail(&node[pre],x))		answer = min(answer,x);	for(int i=head[x]; ~i; i=edge[i].nxt){   		if(i == pre) continue;		if(not linkNode(&node[pre],&node[i],x))			continue;		dfs(edge[i].to,i);	}}bool update(int x,int pre){   	pre ^= 1;	if(x == answer){   		toBeTail(&node[pre],x);		return true;	}	for(int i=head[x]; ~i; i=edge[i].nxt)		if(i != pre and update(edge[i].to,i)){   			linkNode(&node[pre],&node[i]);			return true;		}	return false;}void solve(){   	for(int i=0; i<cntEdge; ++i){   		node[i].dispose();		node[i].id = i;	}	for(int i=1; i<=n; ++i)		Head[i] = tail[i] = nullptr;	for(int i=1,x; i<=n; ++i){   		x = located[i], answer = n+1;		for(int j=head[x]; ~j; j=edge[j].nxt)			if(beHead(&node[j],x))				dfs(edge[j].to,j);		for(int j=head[x]; ~j; j=edge[j].nxt)			if(update(edge[j].to,j)){   				toBeHead(&node[j],x);				break;			}		printf("%d ",answer);	}	putchar('\n');}int main(){   	for(int T=readint(); T; --T){   		input();		solve();	}	return 0;}

后记

考场时思考过“边删除的先后关系”作为判断依据。但是我是 全局性的考虑，就会导致很多问题，无法实现。

——所以 忽略无用信息（或者说 分类讨论？）很重要！我们要充分利用 每个点的邻边的删除顺序是独立的 这一$\text{NB}$特征。