「Test」猴猴吃苹果

题意：一棵 $N$ 个点的数，编号分别为 $0\sim N-1$，每个点上有一个苹果，一开始在编号 $K$ 的点，并且把这个点的苹果吃掉。之后去吃苹果时会把路径上的苹果都吃掉，每天会选择去能吃最多苹果的点，如果有多个点满足条件，就会去编号最小那个点，那么会按照什么顺序开始吃苹果呢？

解析：就是简单的 dfs。

容易发现每天去的点都是以 $K$ 为根的树的叶子节点，于是两次排序：

1. 第一次先以 $K$ 为根，求出深度，同时记录父节点，将点从大到小排序(如果相同则按编号从小到大排)，这些点就是我们准备去的点；
2. 将排完序的点开始遍历，每个点往父节点上跳，直到根节点或被标记为止，跳的同时把路径上的点都标记，记录跳了好多次，这就是到这个点能吃的苹果数量；
3. 将跳的次数从大到小排序，得到答案。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=50101;
int n,k,fa[maxn],head[maxn],cnt,vis[maxn];
struct node
{
	int next;
	int to;
}e[maxn<<1];
struct point
{
	int dep;
	int num;
}a[maxn];
struct answer
{
	int ans;
	int num;
}s[maxn];
int cmp(point a,point b)
{
	if(a.dep==b.dep)
		return a.num<b.num;
	return a.dep>b.dep;
}
int cnm(answer a,answer b)
{
	if(a.ans==b.ans)
		return a.num<b.num;
	return a.ans>b.ans;
}
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs(int u)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v])
			continue;
		fa[v]=u;
		vis[v]=1;
		a[v].dep=a[u].dep+1;
		a[v].num=v;
		dfs(v);
	}
}
int solve(int u)
{
	int sum=0;
	while(!vis[u])
	{
		vis[u]=1;
		u=fa[u];
		sum++;
	}
	return sum;
}
int main()
{
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		add(x,i);
		add(i,x);
	}
	a[k].dep=1;
	a[k].num=k;
	vis[k]=1;
	dfs(k);
	memset(vis,0,sizeof(vis));
	sort(a,a+n,cmp);
	vis[k]=1;
	printf("%d\n",k);
	for(int i=0;i<n;i++)
	{
		if(vis[a[i].num])
			continue;
		else
		{
			s[a[i].num].num=a[i].num;
			s[a[i].num].ans=solve(a[i].num);
		}
	}
	sort(s+1,s+n,cnm);
	for(int i=0;i<n;i++)
		if(s[i].ans)
			printf("%d\n",s[i].num);
	return 0;
}