Yurchiu
An AFO whker.

  首页

  归档

158

  标签

81

  分类

24

  说说

  关于

  留言

  链接

  设置

P5659 [CSP-S2019] 树上的数

Yurchiu,zzy 2021-08-12, 00:59:12 8.4k 隐藏左右两栏 展示左右两栏

首页 / P5659 [CSP-S2019] 树上的数

分享到

这是 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$。

下面是代码。

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))$。

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)$​。

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 号点相邻的边中最大的。要不你想搬个寂寞啊。
• (2) 的优先级是与 3 号点相邻的边中最小的。要不到手的鸭子飞了。

这样对吗？

不对！

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

$$\quad$$

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

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

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

---

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

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

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

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

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

---

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

别忘了说为什么。

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

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

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

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

---

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

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

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

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

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

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 了此题！

#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;
}

---

本文作者：Yurchiu,zzy

本文链接：https://yz-hs.github.io/46fe69313ce6/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 暴搜 毒瘤题 贪心 并查集 链表

最后更新：2023-08-21, 23:18:20

上一页 下一页

By Yurchiu.

随机文章回味旧文

2021，初中毕业

一个 4 人囚徒困境的必胜策略

AFO 有感

2020 新年贺词

ASCII 艺术

BSGS 与 exBSGS

CSP-J1 游记

最近更新旧文更新

[Works] 自白 终章

《幽默报 10》

AFO 有感

OI 之旅

《幽默报》

[Works] 自白

[Idea] 试卷排序

其他物件杂物收纳

Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~

博客信息

文章数目

158

最近更新

08-21

本站字数

350.6k

文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.