洛谷题面

题目大意

小 X 捡到了一台复读机，这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上，完全二叉树是无限延伸的。你将向复读机录入一串指令，这串指令单个字符可以是：

• L：命令机器人向当前节点的左子走；
• R：命令机器人向当前节点的右子走；
• U：命令机器人向当前节点的父亲走（若没有，则命令非法）。

录入指令后，复读机将会把指令无限复读下去。比如命令为 LR，那么机器人会遵从 LRLRLRLR... 一直走下去。

这棵完全二叉树上有一个 \(n\) 个节点的连通块，保证这个连通块包含根节点。连通块上的每个节点都埋有宝藏，机器人到达过的地方如果有宝藏，则会将其开采。如果一个地方没有宝藏，机器人也可以到那里去。机器人也可以反复经过一个地方。

显然，这个连通块本身也是一棵二叉树。

现在，有人告诉了小 X 埋有宝藏的这棵二叉树的前序遍历，小 X 需要寻找到一条尽量短的指令，使得机器人能够挖掘出所有宝藏。

题目分析

发现读入按照前序遍历读入不是非常方便，这里单独考虑一下。

首先自然要给当前节点赋一个编号的。

若当前数字为 \(1\) 或 \(3\)，那么递归进入左子树；

若当前数字为 \(2\) 或 \(3\)，那么递归进入右子树。

代码如下：

inline int input()
{
	int ch=getchar()-'0',p=++ia;
	
	if(ch==1 || ch==3)
	{
		node1[p].ls=input();
	}
	
	if(ch==2 || ch==3)
	{
		node1[p].rs=input();
	}
	
	return p;
}

in function "main()":
	input();

可以发现，进行一次指令之后，我们必然应该将该节点的祖先节点的宝藏全部取走。

设一次指令后我们走到了 \(u\) 点，再执行一次指令后又走到了 \(v\) 点。

那么在 \(u\) 的父子树中经过的路径必然和 \(v\) 和 \(u\) 之间经过的路径一致，为了得到这个最短路径，我们将宝藏树中 \(u\) 的父子树与 \(v\) 和 \(u\) 之间的子树拼在一起，依次类推，最后就能够得到正确的路径了。

如何求出这条指令的长度呢？

每条边一定会经过两次，边有 \(num-1\) 条，所以是 \((num-1)\times 2\)。

是这样吗？可以发现，从拼接树的根到当前循环节的末尾节点只会走一次，所以还需要减去这一段的长度——自然就是节点个数（也就是节点深度） \(present\_depth-1\)。

很简单，可以发现长度就是 \((num-1)\times 2-(present\_depth-1)\)，\(num\) 表示拼接出来的子树的节点个数，\(present\_depth\) 表示当前枚举的 \(u\) 节点的深度。

代码

//2021/12/8

#define _CRT_SECURE_NO_WARNINGS

#include 

#include 

#include //need "INT_MAX","INT_MIN"

#include 

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int INF=INT_MAX;

const int ma=2005;

struct Node
{
	int ls;
	
	int rs;
};

Node node1[ma],node2[ma];

//下面代码中"新树"即"拼接树"qwq 
int ia,ib;//原树大小,新树大小

int pos1,pos2;//原树上 u 的位置,拼接树上末尾节点的位置 

int ans;

inline int input()
{
	int ch=getchar()-'0',p=++ia;
	
	if(ch==1 || ch==3)
	{
		node1[p].ls=input();
	}
	
	if(ch==2 || ch==3)
	{
		node1[p].rs=input();
	}
	
	return p;
}

inline void init()
{
	mst(node2,0);
	
	ib=1;
}

inline void dfs2(int u,int v)//原树位置,新树位置
{
	if(u==pos1 || v==pos2)//到达循环节的末尾节点 
	{
		pos2=v;
		
		v=1;
	}
	
	if(node1[u].ls!=0)
	{
		if(node2[v].ls==0)
		{
			node2[v].ls=++ib;
		} 
		
		dfs2(node1[u].ls,node2[v].ls);
	}
	
	if(node1[u].rs!=0)
	{
		if(node2[v].rs==0)
		{
			node2[v].rs=++ib;
		}
		
		dfs2(node1[u].rs,node2[v].rs);
	}
}

inline void dfs1(int u,int depth)
{
	init();
	
	pos1=u,pos2=0;
	
	dfs2(1,1);
	
	ans=min(ans,(ib-1)*2-(depth-1));
	
	if(node1[u].ls!=0)
	{
		dfs1(node1[u].ls,depth+1);
	}
	
	if(node1[u].rs!=0)
	{
		dfs1(node1[u].rs,depth+1);
	}
}

int main(void)
{
	ans=INF;
	
	input();
	
	dfs1(1,1);
	
	printf("%d\n",ans);
	
	return 0;
}