自动搬运

查看原文

来自洛谷，原作者为

	素质玩家孙1超 天道酬勤！

搬运于2025-08-24 21:33:00，当前版本为作者最后更新于2020-10-29 09:58:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一篇复杂度优秀的做法，随手一交 rank3 ，并且代码更加简洁易懂。

题目：消息传递 。

首先看到题目不难想到直接枚举每一个点作为根进行DP，方程如下

其中 $order$ 表示选择的顺序为 $1,2,3,4......$ 。

在此直接贪心让最大的 $f_j$ 匹配最小的 $order_j$ 即可。

这样直接做树形DP时间复杂度是 $O(n^2 \log \ n )$ 的，但并不是本题的最优解。（当然应为本题的 $n \leq 1000$，这样的算法可以通过）。

考虑如何优化：

我们若仔细思考上面的DP过程不难发现：若对于 $a \not= b$ 有 $a$ 做根和 $b$ 做根时的 $son_x$ 相同 ，那么我们就可以直接拿第一次计算出来的 $f_x$ 直接作为返回值，这样就可以减少许多运算量。

具体化上面的过程：对于每个相同的 $son_x$ 他们都会对应相同的 $father_x$ ，可以用 $dp[x][father_x]$ 纪录答案， 这样记忆化搜索就完成了。

但是空间复杂度不够优，我们把 $dp[x][father_x]$ 用 $father_x$ 连向 $x$ 的单向边代替，这样空间只要开 $O(n)$ 即可。

来大致算一下这样的时间复杂度：

第一次DP时可以把 $n-1$ 条边的DP值纪录，显然一次DP的复杂度是 $O(n \log n)$ ，然而我们只有 $2n-2$ 条单向变，所以总时间大概相当于两次的第一次DP，复杂度仍然是 $O(n \log n)$。

我自认为我的代码比一些题解写的简洁清晰，当然速度也可以：

#include <bits/stdc++.h>
using namespace std;
const int Maxn=1e3+5;
inline int max(int a,int b){return a>b?a:b;}
inline int R()
{
    char c;int res,sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    return res*sign;
}
int n,m,First[Maxn],to[Maxn*2],Next[Maxn*2],dp[Maxn*2],cnt,ans[Maxn],M=1<<30,num;
inline void add(int z,int y)
{
    Next[++cnt]=First[z];
    First[z]=cnt;
    to[cnt]=y;
}
int dfs(int pos,int father ,int fr)
{
    if(fr&&dp[fr]) return dp[fr];
    int res=0;
    priority_queue<int>q;
    for(int k=First[pos];k;k=Next[k])
    {
        if(to[k]==father) continue;
        q.push(dfs(to[k],pos,k));
    }
    for(int i=1;!q.empty();i++,q.pop())
    res=max(res,q.top()+i);
    return dp[fr]=res;
}
int main()
{
    n=R();
    int x;
    for(int i=2;i<=n;i++)
    {
        x=R();
        add(i,x);
        add(x,i);
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]=dfs(i,0,0);
        if(ans[i]<M)
            M=ans[i];
    }
    printf("%d\n",M);
    for(int i=1;i<=n;i++)
    if(ans[i]==M) printf("%d ",i);
    return 0;
}