消息传递

传送门

这个题很有意思哎……一开始我还看错题了，以为只要求最大深度最小……

所谓的上下级关系其实只是树形结构的描述，每个人都有机会当根，所以要遍历根节点。因为一个人在每个时间单位之内只能给一个人传消息，我们贪心的想一下，肯定是给子树最大的那一个节点先传消息比较好，这样的话方法就出现啦，我们只要开一个栈来记录一下这个点的所有儿子传递消息完成所用的时间，从大到小排序，那么状态转移的方程就是dp[x] = max(dp[x],dp[i] + i - 1),(注意是max因为这个已经保证最优了)

最后我们比较一下所有点所花费的时间即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')

using namespace std;
typedef long long ll;
const int M = 1005;
const int N = 500005;
const int INF = 1000000009;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct egde
{
    int next,to;
}e[M<<1];

int n,head[M],dp[M],cnt,ecnt,x,ans = INF,b[M];

bool cmp(int x,int y)
{
    return x > y;
}

void add(int x,int y)
{
    e[++ecnt].to = y;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

void dfs(int x,int fa)
{
    int sta[1005] = {0},top = 0;
    for(int i = head[x];i;i = e[i].next)
    {
    if(e[i].to == fa) continue;
    dfs(e[i].to,x);
    sta[++top] = dp[e[i].to];
    }
    sort(sta+1,sta+1+top,cmp);
    rep(i,1,top) dp[x] = max(dp[x],sta[i] + i - 1);
    dp[x]++;
}

int main()
{
    n = read();
    rep(i,2,n) x = read(),add(x,i),add(i,x);
    rep(i,1,n) dfs(i,i),ans = min(ans,dp[i]),b[i] = dp[i],memset(dp,0,sizeof(dp));
    printf("%d
",ans);
    rep(i,1,n) if(b[i] == ans) printf("%d ",i);
    return 0;
}