CF1225F Tree Factory 做题记录

你需要一棵 $n$ 个节点的有根树，节点编号为 $[0,1,...,n-1]$，其中 $0$ 是根节点，且对于任何非根节点 $v$，它的父节点的标号 $p(v)$ 要比它的标号 $v$ 要小。

工厂里所有的树都是用竹子做的（可能不准确但不影响题意理解），这种竹子是有根的树，且每个节点只有一个子节点（除了叶子节点没有子节点），也就是说，它是直线形的。加工前，竹子的顶点可以随意标注。

要加工竹子为一棵树，可以进行这样的操作：选择任意一个不是根节点且父节点也不是根节点的节点 $v$，将它的父节点变成原先父节点的父节点即 $p(p(v))$，而其它节点的父节点都保持不变，$v$ 的子树也不会改变。

效率是至关重要的，所以在加工出所需要的树的前提下你应当最小化操作数。现在请你构造任何最优的操作序列以生成所需要的树

注意：加工出的结果树的标签必须和所需要的树的标签一致，即根节点标签相同，其它所有具有相同标签的子节点 $v$，其父节点标签$p(v)$也应相同。

数据保证任何输入都至少有一种可行的方案，且最优操作序列最多包含 $10^6$ 个操作。

$2\le n\le 10^5$。

考虑时光倒流，把给定的树变成一条链。

显然答案下界是 $n-\text{树高}$，因为每次操作最多让树高增加 $1$。

那么每次找到深度最浅的分叉，把最高的那个子树接到其它随便一个子树上即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int S=500005;

int n,fat[S];
set<int> g[S];
int dep[S];
int tot,ans[S];
int cnt,a[S];

void dfs(int u)
{
	dep[u]=0;
	for(int v:g[u])
	{
		dfs(v);
		dep[u]=max(dep[u],dep[v]);
	}
	dep[u]++;
}

int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++) scanf("%d",&fat[i]),fat[i]++;
	for(int i=2;i<=n;i++) g[fat[i]].insert(i);
	dfs(1);
	int u=1;
	a[++cnt]=u;
	while(!g[u].empty())
	{
		if(g[u].size()>1)
		{
			int lst=0;
			for(int v:g[u]) if(dep[v]>dep[lst]) lst=v;
			g[u].erase(lst);
			while(!g[u].empty())
			{
				int v=*g[u].begin();
				ans[++tot]=lst;
				g[u].erase(v);
				g[v].insert(lst);
				dep[v]=max(dep[v],dep[lst]+1);
				lst=v;
			}
			g[u].insert(lst);
		}
		u=*g[u].begin();
		a[++cnt]=u;
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]-1);
	printf("\n");
	printf("%d\n",tot);
	for(int i=tot;i>=1;i--) printf("%d ",ans[i]-1);
	printf("\n");
	return 0;
}