某个国家有N个城市，编号0 至 N-1，他们之间用N - 1条道路连接，道路是双向行驶的，沿着道路你可以到达任何一个城市。你有一个旅行计划，这个计划是从编号K的城市出发，每天到达一个你没有去过的城市，并且旅途中经过的没有去过的城市尽可能的多（如果有2条路线，经过的没有去过的城市同样多，优先考虑编号最小的城市），直到所有城市都观光过一遍。现在给出城市之间的交通图T，以及出发地点K，你来设计一个旅行计划，满足上面的条件。例如：
(K = 2)
第1天 从2到0 (城市 1 和 0 变成去过的)
第2天 从0到6 (城市 4 和 6 变成去过的)
第3天 从6到3 (城市 3 变成去过的)
第4天 从3到5 (城市 5 变成去过的)
上图的输入数据为：0 1 2 2 1 4。共7个节点，除节点0之外，共6行数据。
第1个数0表示1到0有1条道路。
第2个数1表示2到1有1条道路。
Input
第1行：2个数N，K(1 <= N <= 50000, 0 <= K <= N - 1)
第2 - N + 1行：每行一个数，表示节点之间的道路。
Output
输出旅行的路线图，即每天到达的城市编号。
Input示例
7 2
0
1
2
2
1
4
Output示例
2 0 6 3 5
————————————————————————————————————————————————————
以下搬自51nod题解
考虑将树根设为K，观察到以下结论：
1. 每次必然会走到叶子，否则可以继续向下走到叶子，使得访问的点增多。
2. 考虑每次访问到的未访问的点，一定是与叶子相连的、在叶子到点K路径上的一条连续的链，
所以问题可以转化为：
令每个叶子分别支配一条链，使得标号小的点尽量支配多的点，最后根据支配的点数多少、标号大小依次访问。
以做法可以是树上贪心，从深到浅依次确定每个点被其子树里哪个叶子支配，
然后使得那个点的支配点个数加一，
最后用基数排序排出支配点数降序、标号大小升序即可。
当然我懒 所以写的是sort代替基排
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=50007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } char s[23];int len; inline void outx(int x) { if(!x){putchar('0');return;} while(x)s[++len]=x%10,x/=10; while(len)putchar(s[len--]+48); } int T,n,rt; int first[M],cnt; struct node{int to,next;}e[M*2]; void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;} void insert(int a,int b){ins(a,b); ins(b,a);} int sum; struct pos{int d,pos;}p[M]; bool cmp(pos a,pos b){return a.d!=b.d?a.d>b.d:a.pos<b.pos;} void dfs(int x,int fa,int deep){ bool f=true; for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(now!=fa) f=false,dfs(now,x,deep+1); } if(f&&x!=rt) p[++sum].pos=x,p[sum].d=deep; } int vis[M]; struct Ans{int h,pos;}q[M]; bool qcmp(Ans a,Ans b){return a.h!=b.h?a.h>b.h:a.pos<b.pos;} int find(int x,int fa){ if(vis[x]||x==rt) return 1; for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(now==fa) continue; if(find(now,x)) return T++,vis[x]=1,1; } return 0; } int main() { int x; n=read(); rt=read(); for(int i=1;i<n;i++) x=read(),insert(i,x); for(int i=1;i<=n;i++) p[i].pos=i; dfs(rt,-1,0); sort(p+1,p+1+sum,cmp); for(int i=1;i<=sum;i++){ q[i].pos=p[i].pos; T=0; find(p[i].pos,-1); q[i].h=T; } sort(q+1,q+1+sum,qcmp); printf("%d ",rt); for(int i=1;i<=sum;i++) printf("%d ",q[i].pos); return 0; }