P5659 [CSP-S2019] 树上的数

发表于 更新于 分类于 ， ， 阅读次数： 作者 Yurchiu ， zzy

这是 Yurchiu 讲课用的讲义。因为是用 Markdown 写的，所以可以直接复制在这里。

P5659 [CSP-S2019] 树上的数

闲话

  • 既然我们又分到了一个黑题，自然要创新一下讲课形式——不用 PPT，而是用讲义！

    或者说，因为这个题兼具思维难度性和代码复杂性，而 PPT 的形式不方便展示代码，所以就用了这个形式。

  • 然后除非大佬们开了防火墙，“文件接收柜”里面应该已经有了今天讲课的资源包。

  • 本讲义有很多提问环节，如果大佬们同步看的话，请不要偷看答案哦！

  • 由于讲课的人水平所限，可能有不清楚或者错误的地方，欢迎指出！

  • 插一嘴，Typora 这个 Markdown 编辑器真好用！

题意

给定一个大小为 \(n\) 的树，它共有 \(n\) 个结点与 \(n - 1\) 条边，结点从 \(1 \sim n\) 编号。初始时每个结点上都有一个 \(1 \sim n\) 的数字，且每个 \(1 \sim n\) 的数字都只在恰好一个结点上出现。

接下来你需要进行恰好 \(n - 1\) 次删边操作，每次操作你需要选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。

\(n - 1\) 次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字 \(1 \sim n\) 所在的结点编号依次排列，就得到一个结点编号的排列 \(P_i\)。现在请你求出，在最优操作方案下能得到的字典序最小的 \(P_i\)。

如上图，蓝圈中的数字 \(1 \sim 5\)​​ 一开始分别在结点 ②，①，③，⑤，④。按照 (1)，(4)，(3)，(2) 的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为 ①③④②⑤，该排列是所有可能的结果中字典序最小的。

数据范围

测试点编号 \(n \leq\) 特殊性质
\(1 \sim 2\) \(10\) 无
\(3 \sim 4\) \(160\) 树的形态是一条链
\(5 \sim 7\) \(2000\) 同上
\(8 \sim 9\) \(160\) 存在度数为 \(n - 1\) 的结点
\(10 \sim 12\) \(2000\) 同上
\(13 \sim 16\) \(160\) 无
\(17 \sim 20\) \(2000\) 无

对于所有测试点：\(1 \leq T \leq 10\)，保证给出的是一个树。

点击查看题解

题解

本题解是把 luogu 的各个题解缝在一块，而形成的题解。我是裁缝。

0x00 前置知识

  • 生成全排列
  • 并查集
  • 链表
  • 贪心

生成全排列

这个我们不必多说吧，诸位大佬肯定都会。通俗来讲，就是通过 dfs 在每一位填数字。

并查集

建议看某菜鸡的 Blog。

  • link1，以模板为主。
  • link2，以例题为主。

链表

一般而言链表都是用指针写的，用数组模拟有你好受的。而指针是个神奇的东西，对初学者极不友好。其实也没啥好说的，就问问你当年是怎么理解链式前向星的。

主要有以下几点：

  • 存储每个节点的地址，且每个节点都有后继的地址；
  • 必要时也可以储存指向自己前驱的地址；
  • 用指针时要注意边界的判断。

话说大家真的彻底明白链式前向星的工作原理了吗，当初为了理解这东西我费了九牛二虎之力。

其实本题可以用链表做。由于时间有限，赶不出利用链表实现的代码。

贪心

可以当作进阶的 DP。然而，这需要严格证明。

0x01 暴搜

用 \(O(n!\times n)\)​​​​​​ 的时间复杂度，得到删边顺序的全排列，再进行模拟，更新答案。这样您就可以得到 10 分了（考场很少有能超过 10 分的人，可以认为是考场满分解）。

相信大家都会生成全排列吧（不会吧不会吧，不会真有人不会吧）。

想拿这 10 分，可不容易。一些注意事项：

  • 注意输入输出格式。做题不审题不是好习惯。

    第二行 \(n\) 个整数，第 \(i\) （\(1 \leq i \leq n\)） 个整数表示数字 \(i\)​​ 初始时所在的结点编号。

    将数字 \(1 \sim n\) 所在的结点编号依次排列，就得到一个结点编号的排列 \(P_i\)。求出在最优操作方案下能得到的字典序最小的 \(P_i\)。

  • 注意模拟时，交换的是一条边两端的数字，所以注意枚举的是 \(n-1\) 的全排列，交换也是枚举到 \(n-1\)。

下面是代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
namespace Force//暴力 
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=2000+10,inf=2147483647;
	struct edge{ll u,v;}e[N*2];
	ll n,num[N],vis[N],a[N],ans[N],tmp[N],ump[N];
	//P 是排列 
	//点的个数 点上的数字 生成P要用到 P 最小的P 点上的数字 数字所在编号 
	void solve()
	{
		for(ll i=1;i<=n;i++)
			tmp[i]=num[i];//因为下面要用到 num，所以复制一遍防止出锅 
		for(ll i=1;i<=n-1;i++)//注意是边的全排列 
			swap(tmp[e[a[i]].u],tmp[e[a[i]].v]);//按照题意 ~~膜你~~ 模拟 
		ll flag=1;//判断是否更新答案 
		for(ll i=1;i<=n;i++)
			ump[tmp[i]]=i;//注意判断字典序是以数字为序，点的编号的排列 
		for(ll i=1;i<=n;i++)//判断字典序的大小 
		{
			if(ump[i]>ans[i]) {flag=0;break;}//这种特性启发了我们 
			if(ump[i]<ans[i]) break;//在后面可以利用贪心求解 
		}
		if(!flag) return;
		for(ll i=1;i<=n;i++) ans[i]=ump[i];//更新答案 
	}
	void dfs(ll step)//必会技能：生成全排列 
	{
		if(step>=n)
		{
			solve();
			return;
		}
		for(ll i=1;i<=n-1;i++)
		{
			if(vis[i]) continue;
			vis[i]=1;a[step]=i;
			dfs(step+1);
			vis[i]=0;
		}
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			for(ll i=1;i<=n;i++)
			{
				scanf("%lld",&a);
				num[a]=i;//注意题目输入格式，对于正解来说比较方便 
				ans[i]=inf;
			}
			for(ll i=1;i<=n-1;i++)
			{
				scanf("%lld%lld",&a,&b);
				e[i].u=a,e[i].v=b;
			}
			dfs(1);
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		}
		return;
	}
}

0x02 菊花图

菊花图有一些比较友好的特性。设菊花图的花心是 \(u\)​，与其相邻的点是 \(x_i\)。发现在删边时，\(x_i\) 固定了 \(u\) 的值（因为 \(x_i\) 除了 \(u\)，与其他的点没有任何关系，既然边 \(<u,x_i>\) 被删掉了，那么这个点的数值也就不会被改变了），而 \(x_i\) 原先的值到了 \(u\)​​，等待下一次被固定。

结合下面的动图进行理解。

容易发现，这个过程有点像一个环。假如将拆边描述为一个排列 \(p_1,p_2,...,p_{n-1}\)​（\(\forall1\le i<n ,p_i\not=u\)​）​，也就是说，你按顺序拆掉了 \((u,p_1),(u,p_2),..,(u,p_{n-1})\)​，那么最后，原来根上的数字 \(a_u\)​ 会去到 \(p_1\)​，原来 \(p_{i}\)​ 上的数字 \(a_{p_i}\)​ 会去到 \(p_{i+1}\)​，原来 \(p_n\)​ 上的数字 \(a_{p_n}\)​ 会去到 \(u\)​。如果我们将点按照 \((u,p_1,p_2,\dots,p_n)\)​​ 的顺序排成一个环的话，整个操作就相当于将每个点上的数字向后移了一位。

而本题目标肯定是尽量把最小的数字给转移到最小的编号上，而且转移的方案（即转移路线）有且仅有一个。

于是很容易地想到一个贪心的构造环（构造拆边顺序）的方法。

按照 \(1,2,3,...,n\)​​​​​​（数字）​​​​​ 的顺序，每个数字从自己所在的点选择在环上面的下一个点（就是说这个数字要搬运到哪里）。那么每次在合法的情况下选标号最小的节点即可。这个方法非常重要，因为后面的解都用到了这个思路。

那如何判断合法呢？

建一个新图。把“搬运点”的过程，当做是连边。就像动图一样，如果一个点 \(x\) 上的数字要搬运到点 \(y\)，就在新图上连一条有向边 \(<x,y>\)。我们容易发现，一个点只能最多有一条入边，一条出边，这样才是合法的。比如，\(x\rightarrow y\rightarrow z\) 是合法的，因为点 \(x\) 上的数字到达点 \(y\) 时，\(y\) 上的数字又正好到达了 \(u\)，就可以到达 \(z\) 了。如果从一个点发出多个有向边，或多个有向边指向一个点，这很明显是不合法的。

相信各位大佬都已经看出来了，这样在新图中会出现许多链。并且，在最后还会形成一个大环。这样，就和我们前面所述的拆边过程契合了。

所以，在环还没有封闭的时候，请注意它们都还是一些链，所以不要出现提前成环提前自闭的情况，并保证最后会出现一个大环而不是若干个小环。

利用用并查集维护，方便地判断是否成环。

下面是代码。时间复杂度是 \(O(n^2\alpha(n))\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
namespace Flower
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=2000+10,inf=2147483647;
	struct UFDS//并查集 
	{
  		ll dad[N],n;
    	void init(ll p){ n=p; for(ll i=1;i<=n;i++) dad[i]=i; }
    	ll find(ll x)//非递归写法，你值得拥有 
    	{   
           	while(x!=dad[x])
            	x=dad[x]=dad[dad[x]];//路径压缩 
         	return x;
    	}
    	void merge(ll x,ll y)
    	{
           ll d1=find(x),d2=find(y);
           dad[d1]=d2;
           return;
    	}	
    	bool check(ll x,ll y)
    	{
           ll d1=find(x),d2=find(y);
           if(d1==d2) return 1;
           return 0;
    	}
	}U;
	ll n,num[N],id[N],vis[N],ans[N];
	//结点数 点上的数字 数字所在编号 是否访问过 
	void solve()
	{
		U.init(n);
		memset(vis,0,sizeof(vis));
		//对于新图来说，vis 数组防止出现一个点连到链的中间的情况 
		for(ll i=1;i<=n;i++)//枚举数字 
		{
			for(ll j=1;j<=n;j++)//贪心地选编号小的点 
			{
				if(vis[j]||(i!=n&&U.check(id[i],j))) continue;
				//首先保证不要破坏链，或者说重复搬运到一个点
				//其次不要使链提前自闭（当枚举到最后一个时就可以自闭了） 
				ans[i]=j;vis[j]=1;U.merge(j,id[i]);break;
				//加入有向边 <id[i],j> 表示删边的先后与相邻关系
				
				//由于并查集的特性（或者说我们已经用 vis 数组进行维护了），
				//实际上 merge 的两个参数并没有先后关系 
			}
		}
		return;
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			for(ll i=1;i<=n;i++)
			{
				scanf("%lld",id+i);
				num[id[i]]=i;
			}
			for(ll i=1;i<=n-1;i++)//好像连图都没用到 
				scanf("%lld%lld",&a,&b);
			solve(); 
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		} 
		return;
	}
}

想必各位大佬已经发现了，读进来的图似乎压根没用到！除了骗分。

原因是，我们对于菊花图上的所有节点，都是一视同仁的。节点 \(u\) 也是符合“一个点只能最多有一条入边，一条出边”的限制的。

0x03 链

链有一些比较友好的特性。它是一条类似于线的东西；除了两个端点之外，其他的点度都为 2。

由于特性 1，我们可以以数组的形式方便地进行处理。我们先找到链首（度为 1 的点），进行 dfs，利用 dfs 序来得到点在链中的先后次序，进行处理。

由于特性 2，先抛开特殊的端点不谈，每个点都有两条边相邻。可以保证的是，两条边的删除次序是有时间的先后的。所以我们可以想到，给每个点一个标记，标记左右两边的删除次序，或者说优先级（无限制或未知，左先右后，左后右先）。这里的优先级实际上就是一种拓扑序。

提问一下：比如说左先右后，一定是左面的边删掉后接着就删右面的边吗？

下面举个例子来说明这个优先级。

比如说在 2 上面的数字要去 5：

  • 它离开 2 时，需要保证边 \(<2,3>\) 在边 \(<1,2>\) 之前先被删，否则它就跑到 1 上面去了。
  • 在它被运送途中，需要保证边 \(<2,3>\)，\(<3,4>\)，\(<4,5>\) 被先后删除，不能颠倒。
  • 它到达 5 时，需要保证边 \(<5,6>\) 在边 \(<4,5>\)​ 之前先被删，否则它就跑到 6 上面去了。

这是往右走的情况，往左的情况可自行推导，其实不难（这里要提问一下）。

而最后，我们判定一个方法是否可行，只需要判断它和前面的点的标记是否冲突即可。

下面是代码。时间复杂度是 \(O(n^2)\)​。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
namespace Chain
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=2000+10,inf=2147483647;
	const ll UnLim=0,FirS=1,SecF=2;
	ll n,id[N],ans[N],deg[N];
	ll dfn[N],link[N],tag[N],cnt=0;
	//结点数 数字所在编号 节点的度
	//节点的dfs序 按dfs序排列的节点 按dfs序排列的节点的标记 dfs序的戳 
	struct graph
	{
		struct edge{ll nxt,to;}e[N*2];
		ll head[N],cnt;
		void clear()
		{
			ms(e);ms(head);
			cnt=0;
		}
		void add(ll a,ll b)
		{
			e[++cnt]=(edge){head[a],b};
			head[a]=cnt;
		}
	}G;
	void dfs(ll root,ll dad)
	{
		dfn[root]=++cnt;
		link[cnt]=root;
		for(ll i=G.head[root];i;i=G.e[i].nxt)
		{
			ll son=G.e[i].to;
			if(son==dad) continue;
			dfs(son,root);
		}
	}
	void solve()
	{
		for(ll i=1;i<=n;i++)
			if(deg[i]==1) {dfs(i,i);break;}
		for(ll i=1;i<=n;i++)//枚举数字 
		{
			ll now=dfn[id[i]],des=inf;
			//now 是起始点，des 是终止点
			//各个变量里面到底存的是什么，一定要分清 
			//有什么不明白的地方可以提问！ 
			/*
			   --0-- now --1-- q --2-- w --3-- e --4-- des --5--
			   0 一定是比 1 后删；1 2 3 4 一定先后删；5 一定比 4 先删。 
			*/
			if(tag[now]!=FirS)//向后找目标 
			{
				for(ll j=now+1;j<=n;j++)
				{
					if(tag[j]!=FirS) des=min(des,link[j]);//符合 目的地 的条件，可选 
					if(tag[j]==SecF) break;//不符合 继续走 条件，返回 
					//这里，提一个问题：上面的两个语句能不能互换？为什么？ 
				}
			}
			/*
			   --0-- des --1-- q --2-- w --3-- e --4-- now --5--
			   5 一定是比 4 后删；4 3 2 1 一定先后删；0 一定比 1 先删。 
			*/
			if(tag[now]!=SecF)//向前找目标 
			{
				for(ll j=now-1;j>=1;j--)
				{
					if(tag[j]!=SecF) des=min(des,link[j]);//符合 目的地 的条件，可选 
					if(tag[j]==FirS) break;//不符合 继续走 条件，返回 
				}
			}
			if(dfn[des]>now)//目标在后面 
			{
				for(ll j=dfn[des]-1;j>=now+1;j--) tag[j]=FirS;//一定先后删
				tag[now]=tag[dfn[des]]=SecF;//前面的后删 
			}
			if(dfn[des]<now)//目标在前面 
			{
				for(ll j=dfn[des]+1;j<=now-1;j++) tag[j]=SecF;//一定先后删
				tag[now]=tag[dfn[des]]=FirS;//后面的后删 
			}
			tag[1]=tag[n]=UnLim;//只有一条边，自然就无所谓了 
			ans[i]=des; 
		}
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			G.clear();
			ms(deg);ms(tag);
			cnt=0;
			scanf("%lld",&n);
			for(ll i=1;i<=n;i++)
				scanf("%lld",id+i);
			for(ll i=1;i<=n-1;i++)
			{
				scanf("%lld%lld",&a,&b);
				G.add(a,b);G.add(b,a);
				deg[a]++;deg[b]++;
			}
			solve();
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		}
		return;
	}
}

0x04 正解

本人已死，有事烧纸。

前方核能！由于难度有亿点大，我尝试把 zzy 的语言搬来，使得讲义语言风格更有趣点。

想必各位巨佬已经不屑于停滞在部分解了 。

想必各位巨佬已经发现了：一个点的邻接边抽象成点后，用有向边表示删除先后关系的话，形成的总是一堆链。这可以通过菊花图认识到这一点。

想必各位巨佬已经发现了：只有共用同一个顶点的边才有删除的先后关系。这可以通过链认识到这一点。

那么恭喜你，链和菊花的做法对我们硬刚正解有很大的启发（正解细节众多，一部分听不懂也没关系，上面加粗的两句话不明白为什么也没关系，后面会讲。建议结合毒瘤的代码来理解）。

那么，我们由链维护边的删除次序想到：能否将这样的维护扩展到多条边的情况？其实是可以的不然我为什么要问这个问题。上面已经说了，只有共用同一个顶点的边才有删除的先后关系。

直接讲有点费事，下面结合图来理解。

我们要将 1 上的数字搬到 4。容易发现：

    1. 的优先级是与 1 号点相邻的边中最大的。要不你想搬个寂寞啊。
    1. 的优先级是与 3 号点相邻的边中最小的。要不到手的鸭子飞了。

这样对吗？

不对！

为什么不对？下面是提问环节！

\[ \quad \]

经过一番研讨，我们发现：

  • 删完 (1) 接着必须删 (2)。要不它就被别人抢去了。

我们神奇地发现，这些条件限制，只需每个点都维护边的删除优先级就可以了！换句话说，只有共用同一个顶点的边才有删除的先后关系。严谨地说，这些限制都是应用在某一点的几条边中的，因此可以单独考虑每个点的情况。

想必各位巨佬已经发现了：维护每个点，不就相当于每个点都是菊花图吗？于是就形成了菊花树，一起来看菊花！

是的。我们在做菊花图时，开了个并查集来维护边的删除次序。想必各位巨佬已经知道了：我们要对于每一个点，都要开一个冰茶几并查集！

那么，对于多个删边的先后关系，我们将它们的边抽象成一个点，删边的先后、紧邻次序抽象成连边，发现它有点像链。

但是这里有个问题：如果一个点删除边的顺序不一定是连续的怎么办？

对于这种情况，我们只需要把它们看成有许多个链，但是它们没有接在一起即可。换句话说，一个点的邻接边抽象成点后，用有向边表示删除先后关系的话，形成的总是一堆链。

情况与单链类似，对于一个数字 \(k\)​ 从起点移动至终点，在路径上有一下几个很重要的性质。有没有大佬总结一下？

别忘了说为什么。

可以根据前面所述，提炼一下。

当大家弄明白之后我们可以继续了。以上一定要明白，下面的得靠自己的修为了。

揭晓答案——几个很重要的性质：

  • 对于起点，其出边一定是这一点第一条被删掉的边。 如果不是，则 k 会被换到其他点上。
  • 对于终点，其入边一定是这一点最后一条被删掉的边。 如果不是，则 k 也会被换到其他点上。
  • 对于中转点，其入边先于出边被删，且在该点的所有边里被删除的顺序是相邻的。 如果不满足，则在中间，数字 k 会被换到其他点上。

思路依然是暴力枚举每个数字，从这个数字的初始位置开始 dfs ，检查路径上的点是否可以作为中转点或终点即可。

这里是这个题的实现中最难的位置，即检查是否满足中转点或终点的条件。这里，使用了并查集来管理边的关系，存储某个点的边的限制连成的链式结构。

对于”几个很重要的性质“的前两个，我的做法是对每一个并查集建了一个虚点，如果一条边的优先级最大，那么由虚点向它连一条边，如果一条边优先级最小，则由它向虚点连一条边。这样就很好搞了。

必须上代码，结合代码讲一讲，否则真的难以理解。必要时画图。理解确实得靠自己的修为了。

时间复杂度是 \(O(n^2\alpha(n))\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
namespace Perfect 
{
	#define ms(a) memset(a,0,sizeof(a))
	#define for(a) for(register a) 
	typedef long long ll;
	const ll N=20000+10,inf=2147483647;
	ll n,id[N],ans[N],deg[N];
	//结点数 数字所在编号 答案 节点的度 
	struct UFDS
	{
		//仍一样，并查集维护的是删边顺序，一条有向边 <u,v>
		//表示边 u 在边 v 之前删，且相邻 
		//可参考菊花图部分进行理解 
		//注意 u 和 v 都是原图中的边 
  		ll dad[N],out[N],in[N],n;
		//out 是一个点有没有出边，in 同理 
		//size 是集合大小，即链的大小 
  		ll size[N];
    	void init(ll p)
		{
			n=p;
			for(ll i=1;i<=n;i++)
			{
				dad[i]=i;
				out[i]=in[i]=0; 
				size[i]=1;
			}
		}
    	ll find(ll x)
    	{
           	while(x!=dad[x])
            	x=dad[x]=dad[dad[x]];
         	return x;
    	}
    	//这里不像菊花图的情况，参数不能颠倒 
    	void merge(ll x,ll y)
    	{
    		//加有向边 <x,y> 
            ll d1=find(x),d2=find(y);
            dad[d1]=d2;size[d2]+=size[d1];
            out[x]=in[y]=1;
		    //标记一个点有了入边或出边
		    //便于判断加入当前点是否会破坏环 
            return;
    	}	
    	ll check(ll x,ll y,ll jud)//简单几行，充满玄机 
    	{
    		if(in[y]||out[x]) return 0;
    		//保证 x 是链尾，y 是链首 
            ll d1=find(x),d2=find(y);
            if(d1==d2&&size[d1]!=jud) return 0;
            //用来判断亿些情况，下面会有大段话来解释 
            return 1;
    	}
	}U;//实际上对于每个点都开了并查集 
	struct graph
	{
		struct edge{ll nxt,to;}e[N*2];
		ll head[N],cnt;
		void clear()
		{
			ms(e);ms(head);
			cnt=0;
		}
		void add(ll a,ll b)
		{
			e[++cnt]=(edge){head[a],b};
			head[a]=cnt;
		}
	}G;
	ll dfs1(ll root,ll edge)//寻径算法 
	{//短短 14 行代码，讲明白不容易啊 qwq
	 //欢迎观看注释比代码长系列 
		ll ret=n+1;//要返回的目标 
		if(root!=edge&&U.check(edge,root,deg[root]+1))
		//接下来判断这个点能不能当作终点。 
		//首先，不是起点才有可能当作终点（废话） 
		//其次。只有最后一个删边，才能保证这个数字不会跑掉。
		
		//这里，root 是个新图虚点，原图虚边，为了保证这个边是最后一个被删掉的。 
		
		//分两种情况：
		//  - 终边未被指定。此时两者不属于同一链，可以连接，表示指定它最后删除。
		//    > check 函数对于不同集合会直接返回 1，表示可行。 
		//  - 此边和起始边在同一链上。即它们先后顺序已确定。
		//    那么我们必须要保证这个删边顺序组成的链中，长度刚好为这个节点的边数。
		//    否则，边不可能删的完。 
		//    > check 函数的参数 3 用来判断边数。
		
		//加 1 的原因，可以类比菊花图的花心。考虑每个点，其周围的边的删边顺序。
		//其删边关系正好是点的度数 +1（想想那个“吃豆人”的动图）。
		//实际上，由于虚点的存在，度数应该 +1。 
			ret=min(ret,root);
		//可以了，取个最小即可。 
		for(ll i=G.head[root];i;i=G.e[i].nxt)
		{
			ll son=G.e[i].to;
			if(edge==i) continue;//别返祖了
			//我们习惯于记录一个点的父亲，其实判断边也行 
			if(U.check(edge,i,deg[root]+1))
			//接下来判断这个点能不能当作中转点。
			
			//实际上也当作是找起始边，因为判断条件相同， 
			//这也是我们 dfs1 传参数刚开始传两个 id[i] 所决定的 
			
			//  - 首先保证不是同一链（我们本来就要连啊） 
			//    > check 函数对于同一链，返回 0。 
			//  - 特殊情况：这个边连接两条链，包含起始边和终边。
			//    这时一定连，防止提前自闭。 
			//    > 由于虚点的存在，实际上 check 函数发现这两条边已经是
			//      同一链了，且恰好就是点的度数，也就返回 1 了。 
			//      不禁让我感慨：check 函数太妙了，直接解决了这么多情况！ 
				ret=min(ret,dfs1(son,i^1));
			//为了方便，异或 1 表示反向边（这是我们连续添加两条有向边决定的）
			//也是奇怪的 cnt 从 (n+1)/2*2+1 开始决定的 
		}
		return ret;
	}
	ll dfs2(ll root,ll edge,ll des)//更新删边条件（并查集） 
	{//这些就很好理解了 
		if(root==des)
		{
			U.merge(edge,root);
			return 1;//为了便于判断到底是要更新哪个路径 
		}
		for(ll i=G.head[root];i;i=G.e[i].nxt)
		{
			ll son=G.e[i].to;
			if(edge==i) continue;
			if(dfs2(son,i^1,des))//沿路径更新 
			{
				U.merge(edge,i);
				return 1;
			}
		}
		return 0;
	}
	void solve()
	{
		for(ll i=1;i<=n;i++)
		{
			ans[i]=dfs1(id[i],id[i]);
			dfs2(id[i],id[i],ans[i]);
		}
		return;
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			G.clear();ms(deg);
			G.cnt=(n+1)/2*2+1;
			//把它变成奇数，且比 n 大
			//便于虚边的建立（虚边都是 1~n 的） 
			
			for(ll i=1;i<=n;i++)
				scanf("%lld",id+i);
			for(ll i=1;i<=n-1;i++)
			{
				scanf("%lld%lld",&a,&b);
				G.add(a,b);G.add(b,a);
				deg[a]++;deg[b]++;
			}
			U.init(G.cnt);//依据 cnt 来开并查集 
			solve();
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		}
		return;
	}
}
int main()
{
	Perfect::main();
	return 0;
}//433 行！

还活着的人举一下手。

0x05 总结

通过这题大家可以发现，此题正解与部分分是紧密相连的，如果没有对部分分的思考，很难直接想到正解。

这启发我们当无法直接想到正解时，可以思考一些此题的部分分，找到部分分与正解之间的联系，进而以迂回的方式找到正解。一些人因过于追求正解，直接跳过部分分思考正解，结果反而无法得到正解。

对于我这种蒟蒻来说，只会 10 分的暴搜。

代码

实在不行就复制，粘贴！恭喜你 A 了此题！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
#include<bits/stdc++.h>
using namespace std;
namespace Force
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=2000+10,inf=2147483647;
	struct edge{ll u,v;}e[N*2];
	ll n,num[N],vis[N],a[N],ans[N],tmp[N],ump[N];
	void solve()
	{
		for(ll i=1;i<=n;i++)
			tmp[i]=num[i];
		for(ll i=1;i<=n-1;i++)
			swap(tmp[e[a[i]].u],tmp[e[a[i]].v]);
		ll flag=1;
		for(ll i=1;i<=n;i++)
			ump[tmp[i]]=i;
		for(ll i=1;i<=n;i++)
		{
			if(ump[i]>ans[i]) {flag=0;break;}
			if(ump[i]<ans[i]) break;
		}
		if(!flag) return;
		for(ll i=1;i<=n;i++) ans[i]=ump[i];
	}
	void dfs(ll step)
	{
		if(step>=n)
		{
			solve();
			return;
		}
		for(ll i=1;i<=n-1;i++)
		{
			if(vis[i]) continue;
			vis[i]=1;a[step]=i;
			dfs(step+1);
			vis[i]=0;
		}
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			for(ll i=1;i<=n;i++)
			{
				scanf("%lld",&a);
				num[a]=i;
				ans[i]=inf;
			}
			for(ll i=1;i<=n-1;i++)
			{
				scanf("%lld%lld",&a,&b);
				e[i].u=a,e[i].v=b;
			}
			dfs(1);
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		}
		return;
	}
}
namespace Flower
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=2000+10,inf=2147483647;
	struct UFDS 
	{
  		ll dad[N],n;
    	void init(ll p){ n=p; for(ll i=1;i<=n;i++) dad[i]=i; }
    	ll find(ll x)
    	{   
           	while(x!=dad[x])
            	x=dad[x]=dad[dad[x]];
         	return x;
    	}
    	void merge(ll x,ll y)
    	{
           ll d1=find(x),d2=find(y);
           dad[d1]=d2;
           return;
    	}	
    	bool check(ll x,ll y)
    	{
           ll d1=find(x),d2=find(y);
           if(d1==d2) return 1;
           return 0;
    	}
	}U;
	ll n,num[N],id[N],vis[N],ans[N];
	void solve()
	{
		U.init(n);
		memset(vis,0,sizeof(vis));
		for(ll i=1;i<=n;i++)
		{
			for(ll j=1;j<=n;j++)
			{
				if(vis[j]||(i!=n&&U.check(id[i],j))) continue;
				ans[i]=j;vis[j]=1;U.merge(j,id[i]);break;
			}
		}
		return;
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			for(ll i=1;i<=n;i++)
			{
				scanf("%lld",id+i);
				num[id[i]]=i;
			}
			for(ll i=1;i<=n-1;i++)
				scanf("%lld%lld",&a,&b);
			solve(); 
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		} 
		return;
	}
}
namespace Chain
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=2000+10,inf=2147483647;
	const ll UnLim=0,FirS=1,SecF=2;
	ll n,id[N],ans[N],deg[N];
	ll dfn[N],link[N],tag[N],cnt=0;
	struct graph
	{
		struct edge{ll nxt,to;}e[N*2];
		ll head[N],cnt;
		void clear()
		{
			ms(e);ms(head);
			cnt=0;
		}
		void add(ll a,ll b)
		{
			e[++cnt]=(edge){head[a],b};
			head[a]=cnt;
		}
	}G;
	void dfs(ll root,ll dad)
	{
		dfn[root]=++cnt;
		link[cnt]=root;
		for(ll i=G.head[root];i;i=G.e[i].nxt)
		{
			ll son=G.e[i].to;
			if(son==dad) continue;
			dfs(son,root);
		}
	}
	void solve()
	{
		for(ll i=1;i<=n;i++)
			if(deg[i]==1) {dfs(i,i);break;}
		for(ll i=1;i<=n;i++)
		{
			ll now=dfn[id[i]],des=inf;
			if(tag[now]!=FirS)
			{
				for(ll j=now+1;j<=n;j++)
				{
					if(tag[j]!=FirS) des=min(des,link[j]);
					if(tag[j]==SecF) break;
				}
			}
			if(tag[now]!=SecF)
			{
				for(ll j=now-1;j>=1;j--)
				{
					if(tag[j]!=SecF) des=min(des,link[j]);
					if(tag[j]==FirS) break;
				}
			}
			if(dfn[des]>now)
			{
				for(ll j=dfn[des]-1;j>=now+1;j--) tag[j]=FirS;
				tag[now]=tag[dfn[des]]=SecF;
			}
			if(dfn[des]<now)
			{
				for(ll j=dfn[des]+1;j<=now-1;j++) tag[j]=SecF;
				tag[now]=tag[dfn[des]]=FirS;
			}
			tag[1]=tag[n]=UnLim;
			ans[i]=des; 
		}
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			G.clear();
			ms(deg);ms(tag);
			cnt=0;
			scanf("%lld",&n);
			for(ll i=1;i<=n;i++)
				scanf("%lld",id+i);
			for(ll i=1;i<=n-1;i++)
			{
				scanf("%lld%lld",&a,&b);
				G.add(a,b);G.add(b,a);
				deg[a]++;deg[b]++;
			}
			solve();
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		}
		return;
	}
}
namespace Perfect 
{
	#define ms(a) memset(a,0,sizeof(a))
	#define for(a) for(register a) 
	typedef long long ll;
	const ll N=20000+10,inf=2147483647;
	ll n,id[N],ans[N],deg[N];
	struct UFDS
	{
  		ll dad[N],out[N],in[N],n;
  		ll size[N];
    	void init(ll p)
		{
			n=p;
			for(ll i=1;i<=n;i++)
			{
				dad[i]=i;
				out[i]=in[i]=0; 
				size[i]=1;
			}
		}
    	ll find(ll x)
    	{
           	while(x!=dad[x])
            	x=dad[x]=dad[dad[x]];
         	return x;
    	}
    	void merge(ll x,ll y)
    	{
            ll d1=find(x),d2=find(y);
            dad[d1]=d2;size[d2]+=size[d1];
            out[x]=in[y]=1;
            return;
    	}	
    	ll check(ll x,ll y,ll jud)
    	{
    		if(in[y]||out[x]) return 0;
            ll d1=find(x),d2=find(y);
            if(d1==d2&&size[d1]!=jud) return 0;
            return 1;
    	}
	}U;
	struct graph
	{
		struct edge{ll nxt,to;}e[N*2];
		ll head[N],cnt;
		void clear()
		{
			ms(e);ms(head);
			cnt=0;
		}
		void add(ll a,ll b)
		{
			e[++cnt]=(edge){head[a],b};
			head[a]=cnt;
		}
	}G;
	ll dfs1(ll root,ll edge)
	{
		ll ret=n+1;
		if(root!=edge&&U.check(edge,root,deg[root]+1))
			ret=min(ret,root);
		for(ll i=G.head[root];i;i=G.e[i].nxt)
		{
			ll son=G.e[i].to;
			if(edge==i) continue;
			if(U.check(edge,i,deg[root]+1))
				ret=min(ret,dfs1(son,i^1));
		}
		return ret;
	}
	ll dfs2(ll root,ll edge,ll des)
	{
		if(root==des)
		{
			U.merge(edge,root);
			return 1;
		}
		for(ll i=G.head[root];i;i=G.e[i].nxt)
		{
			ll son=G.e[i].to;
			if(edge==i) continue;
			if(dfs2(son,i^1,des))
			{
				U.merge(edge,i);
				return 1;
			}
		}
		return 0;
	}
	void solve()
	{
		for(ll i=1;i<=n;i++)
		{
			ans[i]=dfs1(id[i],id[i]);
			dfs2(id[i],id[i],ans[i]);
		}
		return;
	}
	void main()
	{
		ll T,a,b;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			G.clear();ms(deg);
			G.cnt=(n+1)/2*2+1;
			for(ll i=1;i<=n;i++)
				scanf("%lld",id+i);
			for(ll i=1;i<=n-1;i++)
			{
				scanf("%lld%lld",&a,&b);
				G.add(a,b);G.add(b,a);
				deg[a]++;deg[b]++;
			}
			U.init(G.cnt);
			solve();
			for(ll i=1;i<=n;i++)
				printf("%lld ",ans[i]);
			printf("\n");
		}
		return;
	}
}
int main()
{
	Perfect::main();
	return 0;
}