题目链接
https://codeforces.com/contest/1246/problem/D
题解
首先考虑答案的下界是\(n-1-dep\) (\(dep\)为树的深度，即任何点到根的最大边数)，因为每一次操作只会使一个子树内的点深度\(-1\), 也就最多使得最大深度\(-1\). 那么这个下界能否达到呢？答案是肯定的，因为考虑将过程倒过来，每次选择一个子树将它沿某条边向下移动，对于任何一棵非链的树，最深点到根的路径上一定存在分叉，因此就一定可以通过移动使得最大深度\(+1\). 考虑如何构造: 我的做法是依然倒着思考，DFS整棵树，保证最深点所在子树最后遍历，然后得到的遍历序就是输出的第一个序列。从前往后遍历第一个序列，在第二个答案序列中插入数量等于从上一个点DFS到这个点前进的步数的后一个数。 例如从3号点走到4号点，先后退了\(2\)步又前进了\(3\)步，那么就在第二个答案序列中插入\(3\)个\(4\). 至于算法的正确性，手推一下就很显然了。
代码
#include<bits/stdc++.h>
#define llong long long
using namespace std;
inline int read()
{
int x=0; bool f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
if(f) return x;
return -x;
}
const int N = 1e5;
struct Edge
{
int v,nxt;
} e[(N<<1)+3];
int fe[N+3];
int fa[N+3];
int mxd[N+3];
int hvs[N+3];
vector<int> id;
vector<int> opt;
int n,en,cnt;
void addedge(int u,int v)
{
en++; e[en].v = v;
e[en].nxt = fe[u]; fe[u] = en;
}
void dfs1(int u)
{
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v;
if(v==fa[u]) continue;
dfs1(v);
if(mxd[v]+1>mxd[u]) {mxd[u] = mxd[v]+1,hvs[u] = v;}
}
}
void dfs2(int u)
{
id.push_back(u);
for(int i=1; i<=cnt; i++) opt.push_back(u);
cnt = 0;
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v;
if(v==fa[u]||v==hvs[u]) continue;
dfs2(v);
}
if(hvs[u]) {dfs2(hvs[u]);}
cnt++;
}
int main()
{
scanf("%d",&n);
for(int i=2; i<=n; i++) {scanf("%d",&fa[i]); fa[i]++; addedge(fa[i],i); addedge(i,fa[i]);}
dfs1(1);
dfs2(1);
for(int i=0; i<id.size(); i++) printf("%d ",id[i]-1); puts("");
printf("%d\n",opt.size());
for(int i=0; i<opt.size(); i++) printf("%d ",opt[i]-1); puts("");
return 0;
}
