第1行：2个数N，K(1 <= N <= 50000, 0 <= K <= N - 1)
第2 - N + 1行：每行一个数，表示节点之间的道路。
输出旅行的路线图，即每天到达的城市编号。
7 2
0
1
2
2
1
4
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\n",rt); for(int i=1;i<=sum;i++) printf("%d\n",q[i].pos); return 0; }
原文：http://www.cnblogs.com/lyzuikeai/p/7396079.html