传送门啦

这个树形dp就没那么简单了，运用了一下贪心的思想

不同的排序方法对应着不同的转移方程，如果我们用 $ f[x] = max(f[x] , b[i] +cnt - i + 1) $ 来进行转移就要从小往大排，才能使f[x]小，如果用 $ f[x] = max(f[x] , b[i] + i - 1) $ 来转移就要从大往小排序。

第一个转移方程：$ cnt- i $ 为还有多少个才能到它，然后+1是因为国王这个点信息需要1的时间。即他子树的大小+传递到他的时间+1（向下传递）

第二个转移方程类似。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1005;

inline int read(){

	char ch = getchar();

	int f = 1 , x = 0;

	while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}

	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}

	return x * f;

}

int n,p;

int head[maxn],tot;

int f[maxn],minn=1e9;

int ans[maxn];

struct Edge{

	int to,next;

}edge[maxn << 1];

void add(int u,int v){

	edge[++tot].to = v;

	edge[tot].next = head[u];

	head[u] = tot;

}

void dfs(int x,int fa){

    int b[550],cnt = 0;

    for(int i=head[x];i;i=edge[i].next){

        int v = edge[i].to;

        if(v != fa){

        	dfs(v , x);

        	b[++cnt] = f[v];

        }

    }

    sort(b + 1, b + 1 + cnt );

    for(int i=1;i<=cnt;i++)

        f[x] = max(f[x] , b[i] + cnt - i + 1);

}	

int main(){

	n = read();

	for(int i=2;i<=n;i++){

		p = read();

		add(i , p);

		add(p , i);

	}

	for(int i=1;i<=n;i++){

		memset(f , 0 , sizeof(f));

		dfs(i , 0);

		minn = min(minn , f[i]);

	 	ans[i] = f[i];

	}

	printf("%d\n",minn+1);

	for(int i=1;i<=n;i++)

		if(ans[i] == minn)  printf("%d ",i);

	return 0;

}

第二个：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1005;

inline int read(){

    char ch = getchar();

    int f = 1 , x = 0;

    while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}

    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}

    return x * f;

}

int n,p;

int head[maxn],tot;

int f[maxn],minn=1e9;

int ans[maxn];

struct Edge{

    int to,next;

}edge[maxn << 1];

void add(int u,int v){

    edge[++tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot;

}

bool cmp(int x , int y){

    return x > y;

}

void dfs(int x,int fa){

    int b[550] = {0},cnt = 0;

    for(int i=head[x];i;i=edge[i].next){

        int v = edge[i].to;

        if(v != fa){

        	dfs(v , x);

        	b[++cnt] = f[v];

        }

    }

    sort(b + 1, b + 1 + cnt , cmp);

    for(int i=1;i<=cnt;i++)

        f[x] = max(f[x] , b[i] + i - 1);

    f[x] += 1;

}

int main(){

    n = read();

    for(int i=2;i<=n;i++){

        p = read();

        add(i , p);  add(p , i);

    }

    for(int i=1;i<=n;i++){

        memset(f , 0 , sizeof(f));

        dfs(i , 0);

        minn = min(minn , f[i]);

     	ans[i] = f[i];

    }

    printf("%d\n",minn);

    for(int i=1;i<=n;i++)

        if(ans[i] == minn)  printf("%d ",i);

    return 0;

}