题解 P2018 【消息传递】

· · 题解

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

题目：消息传递 。

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

f_i = \max _{j \in son_i} {\{f_j + order_j\}}

其中 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;
}