你需要一棵 个节点的有根树,节点编号为 ,其中 是根节点,且对于任何非根节点 ,它的父节点的标号 要比它的标号 要小。
工厂里所有的树都是用竹子做的(可能不准确但不影响题意理解),这种竹子是有根的树,且每个节点只有一个子节点(除了叶子节点没有子节点),也就是说,它是直线形的。加工前,竹子的顶点可以随意标注。
要加工竹子为一棵树,可以进行这样的操作:选择任意一个不是根节点且父节点也不是根节点的节点 ,将它的父节点变成原先父节点的父节点即 ,而其它节点的父节点都保持不变, 的子树也不会改变。
效率是至关重要的,所以在加工出所需要的树的前提下你应当最小化操作数。现在请你构造任何最优的操作序列以生成所需要的树
注意:加工出的结果树的标签必须和所需要的树的标签一致,即根节点标签相同,其它所有具有相同标签的子节点 ,其父节点标签也应相同。
数据保证任何输入都至少有一种可行的方案,且最优操作序列最多包含 个操作。
。
考虑时光倒流,把给定的树变成一条链。
显然答案下界是 ,因为每次操作最多让树高增加 。
那么每次找到深度最浅的分叉,把最高的那个子树接到其它随便一个子树上即可。
代码如下:
#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;
}