官方题解：https://blog.csdn.net/qq_62464995/article/details/127493921
题目大意
给出一棵边权为1的树，构造排列p，使得
①p[1]=1
②dis(p[i],p[i+1])<=k
题解
神必防ak题
当k=1时，显然只能是从1开始的一条链
当k>=3时，一定有解，考虑构造：
把树上的点按层黑白黑白染色，dfs遍历整棵树，在第一次进入黑点和第一次走出白点时把点加入p中
最后是1-4-5-2-6-7-3
当k=2时，考虑dp：
设f[i]表示走一步走进i，能否走完i的子树
设g[i]表示从i的父亲跳到i的儿子，能否走完i子树之后走回i
设h[i]表示从i的父亲跳到i的儿子，能否走完i的子树
先不考虑h，考虑f和g的转移
给一个点i的儿子分类，size=1的儿子称为散点，记作x；size>1的儿子才用f/g/h的走法来走，则
f的转移：i(g)xx(f)
g的转移：xx(g')i（g'表示把路径g反转，即从i走完子树后跳到父亲）
（i是当前的根）
发现这样还是不充要，比如下面这一组
20 2
1 2 2 4 4 6 5 5 9 5 7 11 13 3 4 6 4 16 9
那么此时引入h[i]，f的转移多了一条 h（一个儿子，这个儿子走h）
h的转移：xxih / xxg'ih / xxg'igf
（为了方便处理，能走一步到i再走f解决的就不在h里处理，比如gxxf，就可以走一步到i再走f[i]，没必要处理）
（h实际就是先跳进去走g，回到根i之后在另一边走f）
构造方案的话就用双向链表，记录两个方向分别到哪里
注意多次反转+合并之后next[0/1]对应的前/后关系会混乱，所以遍历需要用pre和now一步步走，
同时两条链的合并需要用next[]为空的进行连边；反转直接改变direction，这样就可以O(1)反转+合并，最后O(n)遍历
code
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
//#define file
using namespace std;
class Node{
public:
Node* nx[2];
int val=0;
Node() {nx[0]=nx[1]=nullptr;}
Node(int v) {nx[0]=nx[1]=nullptr;val=v;}
};
Node* NextNode(int pre,Node* &Now)
{
int i;
fo(i,0,1)
if (Now->nx[i]!=nullptr && (Now->nx[i])->val==pre)
return Now->nx[i^1];
fo(i,0,1)
if (Now->nx[i]!=nullptr)
return Now->nx[i];
return nullptr;
}
class List{
public:
int dir=0;
Node* head[2];
List()
{
dir=0;
head[0]=head[1]=nullptr;
}
List(int val)
{
dir=0;
head[0]=new Node(val);
head[1]=head[0];
}
void linkNode(Node* x,Node* y)
{
int i;
fo(i,0,1)
if (x->nx[i]==nullptr)
{
x->nx[i]=y;
return;
}
}
void link(List& another)
{
linkNode(head[dir^1],another.head[another.dir]);
linkNode(another.head[another.dir],head[dir^1]);
head[dir^1]=another.head[another.dir^1];
}
void Reverse()
{
dir^=1;
}
};
int n,K,i,j,k,l,x,y,z;
int a[400001][2],ls[200001],len;
bool f[200001],g[200001],h[200001]; //g ok=>f ok
int Size[200001];
vector<int> ans;
List ans2[200001];
int dis[101][101];
void checker()
{
if (n<=100)
{
fo(k,1,n)
{
fo(i,1,n)
if (i!=k)
{
fo(j,1,n)
if (j!=i && j!=k)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
fo(i,1,n-1)
if (dis[ans[i]][ans[i+1]]>K)
{
cout<<"Oh shit"<<endl;
exit(0);
}
}
}
void Exit()
{
printf("No\n");
exit(0);
}
void New(int x,int y)
{
++len;
a[len][0]=y;
a[len][1]=ls[x];
ls[x]=len;
}
void dfsk3(int Fa,int t,int dep)
{
int i;
if (dep==1) ans.push_back(t);
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
dfsk3(t,a[i][0],dep^1);
if (dep==0) ans.push_back(t);
}
void dfs(int Fa,int t)
{
int i;
Size[t]=1;
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
{
dfs(t,a[i][0]);
Size[t]+=Size[a[i][0]];
}
}
void dfs_dp(int Fa,int t)
{
int i,id1=0,id2=0,id3=0;
vector<int> sandian;
sandian.clear();
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
{
if (Size[a[i][0]]==1)
sandian.push_back(a[i][0]);
else
{
if (!id1)
id1=a[i][0];
else
if (!id2)
id2=a[i][0];
else
if (!id3)
id3=a[i][0];
else
Exit();
}
}
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
dfs_dp(t,a[i][0]);
if (t==2)
n=n;
// f:
if (!id1) f[t]=1;
else
if (sandian.size()==0 && h[id1]) //h
f[t]=1;
else
if (!id2)
{
if (f[id1] || g[id1]) //xxf or gxx
f[t]=1;
}
else
if (!id3)
{
if (f[id1] && g[id2] || f[id2] && g[id1]) //gxxf
f[t]=1;
}
else
f[t]=0;
// g:
if (!id1 && sandian.size()>0) g[t]=1;
else
if (!id2)
{
if (g[id1]) //xxg'
g[t]=1;
}
else
g[t]=0;
// h: xxh or xxg'hxx or xxg'gf
if (!id1)
h[t]=0;
else
if (!id2)
{
if (sandian.size()>0 && h[id1])
h[t]=1;
}
if (!id3)
{
if (g[id1] && h[id2] || g[id2] && h[id1])
h[t]=1;
}
else
{
if (f[id1] && g[id2] && g[id3] || f[id2] && g[id1] && g[id3] || f[id3] && g[id2] && g[id1])
h[t]=1;
}
}
void dfs_con(int Fa,int t,int tp) //tp=0f/1g/2h
{
int i,id1=0,id2=0,id3=0,sz;
vector<int> sandian;
sandian.clear();
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
{
if (Size[a[i][0]]==1)
sandian.push_back(a[i][0]);
else
{
if (!id1)
id1=a[i][0];
else
if (!id2)
id2=a[i][0];
else
if (!id3)
id3=a[i][0];
else
Exit();
}
}
sz=sandian.size();
if (tp==0) // f:
{
if (!id1) //xxx
{
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]);
}
else
if (sandian.size()==0 && h[id1]) //h
{
dfs_con(t,id1,2);
ans2[t].link(ans2[id1]);
}
else
if (!id2)
{
if (f[id1]) //xxf
{
dfs_con(t,id1,0);
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]);
ans2[t].link(ans2[id1]);
}
else //gxx
{
dfs_con(t,id1,1);
ans2[t].link(ans2[id1]);
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]);
}
}
else //gxxf
{
if (f[id2] && g[id1]) swap(id1,id2);
dfs_con(t,id1,0);
dfs_con(t,id2,1);
ans2[t].link(ans2[id2]);
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]);
ans2[t].link(ans2[id1]);
}
}
else // g:
if (tp==1)
{
if (!id1 && sandian.size()>0) //xxxt
{
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]);
ans2[t].Reverse();
}
else
if (!id2) //xxg't=(tgxx)'
{
dfs_con(t,id1,1);
ans2[t].link(ans2[id1]);
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]);
ans2[t].Reverse();
}
else
g[t]=0;
}
else
if (tp==2) //h
{
if (!id1)
h[t]=0; //can't
else
if (!id2)
{
if (sandian.size()>0 && h[id1]) //xxth=(txx)'h
{
dfs_con(t,id1,2);
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]); //xx
ans2[t].Reverse(); //(txx)'h
ans2[t].link(ans2[id1]);
}
}
else
if (!id3) //xxg'th
{
if (g[id2] && h[id1]) swap(id1,id2);
// if (g[id1] && h[id2] || g[id2] && h[id1])
dfs_con(t,id1,1);
dfs_con(t,id2,2);
ans2[t].link(ans2[id1]); //g
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]); //xx
ans2[t].Reverse(); //tgxx => xxg't
ans2[t].link(ans2[id2]); //h
}
else //xxg'tgf
{
if (f[id2] && g[id1] && g[id3]) swap(id1,id2);
else
if (f[id3] && g[id1] && g[id2]) swap(id1,id3);
// if (f[id1] && g[id2] && g[id3] || f[id2] && g[id1] && g[id3] || f[id3] && g[id2] && g[id1])
dfs_con(t,id1,0);
dfs_con(t,id2,1);
dfs_con(t,id3,1);
ans2[t].link(ans2[id2]); //g1
fo(i,0,sz-1)
ans2[t].link(ans2[sandian[i]]); //xx
ans2[t].Reverse(); //tgxx => xxg't
ans2[t].link(ans2[id3]); //g2
ans2[t].link(ans2[id1]); //f
}
}
}
int main()
{
#ifdef file
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
ans.push_back(0);
memset(dis,1,sizeof(dis));
scanf("%d%d",&n,&K);
fo(i,2,n)
{
scanf("%d",&x),New(x,i),New(i,x);
if (n<=100)
dis[x][i]=dis[i][x]=1;
}
if (K==1)
{
x=1,l=0;
while (1)
{
bool find=0;
ans.push_back(x);
for (i=ls[x]; i; i=a[i][1])
if (a[i][0]!=l)
{
l=x;x=a[i][0];
find=1;
break;
}
if (!find) break;
}
if (ans.size()!=n+1) {printf("No\n");return 0;}
}
else
if (K>=3)
{
dfsk3(0,1,1);
}
else
{
fo(i,1,n) ans2[i]=List(i);
dfs(0,1);
dfs_dp(0,1);
if (f[1])
{
dfs_con(0,1,0);
Node* Now=ans2[1].head[ans2[1].dir];
l=0,x=1;
while (Now!=nullptr)
{
x=Now->val;
ans.push_back(x);
Now=NextNode(l,Now),l=x;
}
}
else
Exit();
}
if (ans.size()!=n+1) Exit();
checker();
printf("Yes\n");
printf("%d",ans[1]);fo(i,2,n) printf(" %d",ans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
//20 2
//1 2 2 4 4 6 5 5 9 5 7 11 13 3 4 6 4 16 9
//Yes
//20 2
//1 2 2 2 1 3 4 6 3 6 2 5 11 8 8 15 11 13 17
//No
//12 2
//1 2 3 3 5 3 7 3 4 2 4
//Yes