自动搬运

查看原文

来自洛谷，原作者为

	天泽龟 理想与孤独 | My Blog: http://tzturtle.moe

搬运于2025-08-24 22:12:22，当前版本为作者最后更新于2019-10-22 01:06:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题思维挺新颖的，一时候拿到还真不一定做出来，本人也是看了讲评才明白的，真是让人叹为观止。

可惜的是，很多人表示并不明白官方题解是啥意思，故写文以记之，希望可以帮助更多人。

首先我们要明白题目的意思：给定一个无限二叉树，并给定以1号节点为根标记一个小的染色二叉树，找一个最小遍历循环节（以下简称，$S$）可以通过无数次循环走遍这个染色二叉树（以下简称，$T$）。

由于二叉树的大小是无限的，所以可以保证如果$S$合法（即不会跑到根的父亲），就可以一直走下去。当然，如果出现遍历到的节点$\notin T$，这并不影响循环节的合法性。

我们来考虑正解。很明显的是，每复读一遍$S$，你一定仅会到达当前节点子树中的某一节点。当该节点 $\notin T$ 时，你之后一定会越偏越远，再也遍历不到$T$的节点了，整个复读就此结束。而我们要做的，就是确保我们构造的$S$可以在此之前遍历完$T$的所有节点。

又由于每次复读一遍$S$，所到达节点$x$ 与 当前节点$now$ 的相对位置是不变的，而且下一步我们也仅会遍历$x$子树中的元素了，这就意味着我们要遍历到所有$p\in T$，且$p$属于$now$的子树但不属于$x$的子树，这些点若此时不被遍历就永远没机会了。

基于以上两点，我们不妨通过枚举根节点通过一次循环节可到达的节点$X$，以此不断复读下去直到离开$T$，同时我们把所有以$now$为根的，不包含$x$的子树 的染色连通块截取下来，并将它们以$now$为根，合并成一个染色"并"树（这里引用了官方题解的说法），很明显的是该并树包含了我们一次操作中所要包含到的所有节点。

若该树的大小为$size$，与$X$相对位移为$x$（其实就是深度），那么最优的构造方案即为$2*(size-1)-x$，即除了$X$及其链上的点只走一次外，其他均走2次。

由于我们枚举$X$是$O(N)$的，建个并树也是$O(N)$的，所以$O(N^2)$稳过~

当然，理论很简单，但在代码实现方面仍有些小问题。比方说这个"并"树，我们到底是如何得到的呢？

我们可以类比线段树合并的思想（反正都是二叉树），若原来没有点就新建一个，原来有点的话就直接合并，最后特判一下别搜到$x$的子树就行啦，详细可以看我丑陋的代码：

#include <iostream>
#include <cstring>
#define inf 2147483647
using namespace std;

struct ed{
	int ls,rs,f,sz,dd;
}p[3000],c[3000];
string s;
int st,lq,ans=inf/2;

int build(int fa,int poi)  //初始化建树 
{
	p[poi].f=fa; p[poi].sz=1; p[poi].dd=p[fa].dd+1; 
	if (s[poi]=='3') {
		p[poi].ls=build(poi,poi+1), p[poi].sz+=p[p[poi].ls].sz;
		p[poi].rs=build(poi,poi+p[poi].sz), p[poi].sz+=p[p[poi].rs].sz;}
	if (s[poi]=='2') 
		p[poi].rs=build(poi,poi+1), p[poi].sz+=p[p[poi].rs].sz;
	if (s[poi]=='1')
		p[poi].ls=build(poi,poi+1), p[poi].sz+=p[p[poi].ls].sz;
	return poi;
}

int gd(int now,string t)
{	int l=t.size();
	for (int i=0;i<l;i++) now=((t[i]=='L')?p[now].ls:p[now].rs);
	return now;
}

int merge(int now,int cs,int sp)  //求并树 
{	
	if (!now) return cs;
	if (!cs) cs=++st; c[cs].sz=1;
	if (now==sp) return cs;
	c[cs].ls=merge(p[now].ls,c[cs].ls,sp); c[cs].sz+=c[c[cs].ls].sz;
	c[cs].rs=merge(p[now].rs,c[cs].rs,sp); c[cs].sz+=c[c[cs].rs].sz;
	return cs;
}

int find(string rep)
{
	int now=1,last=0;
	while (now){  //若now=0，则退出 
		last=now , now=gd(now,rep); 
		merge(last,1,now);
	}
	return c[1].sz;
}

void search(int now,string rep){  //找相对位置 
	int cnt=0;
	if (now==0) return;
	if (now!=1) {
		memset(c,0,sizeof(c)); st=1; cnt=find(rep);
		ans=min(ans,2*(cnt-1)-p[now].dd+1);
	}
	
	search(p[now].ls,rep+'L');
	search(p[now].rs,rep+'R');
}

int main()
{
	cin>>s; lq=s.size(); s='.'+s; 
	build(0,1);
	search(1,"");
	cout<<ans<<endl;
}

写题解比敲代码耗时长，困死了