CF1225F Tree Factory 做题记录

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

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

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

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

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

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

2n1052\le n\le 10^5

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

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

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

代码如下:

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