题解 P2018 【消息传递】

· · 题解

这里主要介绍一个O(n\log_2n)的算法

虽然对于这道题O(n^2\log_2n)暴力枚举根已经可以AC了，但优化是无止境的

首先可以想出这道题对于一个确定的根的dp

再以任意点root为主根前提下

我们设f_{i}表示以i为根不计算根被传递到消息时间,把消息传到i为根的子树的最短时间

当i的子树均被计算完毕时

\displaystyle{f_i=\max_{j\in son_i}}\{f_j+order_j\}

其中order_j表示j是i的孩子中第order_j个选的，也就是他在i收到消息后第order_j个时间收到消息的

很容易想到贪心，我们让f_j值大的先传

单次复杂度O(n\log_2n)

但这样做需要枚举根，最终复杂度O(n^2\log_2n)

瓶颈在于什么,仔细思考我们会发现其实是我们确定了向“下”传的顺序，而因此很多子树的信息在不同的根下实际上是一样的

什么意思，我们看一下这幅图

在fa,i,brother1,brother2作根的时候,以j为根的子树的形态没有一点改变

我们有没有办法一次计算这些信息呢

有的，那就是所谓的二次扫描与换根法

在李煜东的书里介绍了这个算法并给出了一个例题，但这个例题会更为复杂一些

我先重复一下这个算法流程

我们用这道题来看如何实现

对于down部分是类似的

设down_{i}表示不计算根被传递到消息时间,把消息传到i为根的子树的最短时间

我们在计算完了i的儿子j后来更新i

\displaystyle{down_i=\max_{j\in son_i}}\{down_j+order_j\} ```cpp inline void tree_dp(re int x){ re int i,y,res=0;re vector<int> son; for(i=h[x];i;i=e[i].next){ y=e[i].to; tree_dp(y); son.push_back(dpson[y]); } sort(son.begin(),son.end(),cmp); for(i=0;i<(int)son.size();++i)res=max(res,son[i]+i+1); dpson[x]=res; } ``` 而对于$up$部分 设$up_{i}$表示**不计算根被传递到消息时间,把消息传到除了$i$为根的子树的节点**的最短时间 可能很难理解，我们用一张图来展示 ![upanddown.png](https://i.loli.net/2019/08/22/GOwKhgEe9qmdTya.png) 可以形象的理解为$down$对应的部分是在有根情况下向“下”的很多支子树,而$up$对应的部分是向“上”的那一支 我们在计算完了$j$的父亲$i$后来更新$j \displaystyle{up_j=\max\{up_i+order'_i~,\max_{k\in son_i\vee k\ne j}}~\{down_k~+~order'_k\}~\}

用这幅图理解一下,up_j保存的是来自父亲i的一支,其中包含了他父亲的父亲那一支up_j,也包含了i的父亲除了i的其他儿子支

注意一下:为了处理方便，我们并不一开始显式去掉i的儿子j,而是吧down_k和up_i加进去排序,在需要求出up_j时我们二分查找j的位置,并把这个位置后面的位置的order值减一，因为我们在我们一开始的假设中，选j实际上是花了一个时间的，但实际并没有.实际操作上可以利用前缀和后缀\max来实现

inline void change_root(re int x){
    re int i,y,pos;re vector<int> son;
    for(i=h[x];i;i=e[i].next){y=e[i].to;son.push_back(dpson[y]);}if(fa[x])son.push_back(dpfa[x]);
    sort(son.begin(),son.end(),cmp);
    for(i=0;i<(int)son.size();++i)t[i]=son[i]+i+1;
    *maxl=t[0];for(i=1;i<(int)son.size();++i)maxl[i]=max(maxl[i-1],t[i]);
    maxr[son.size()-1]=t[son.size()-1];for(i=son.size()-2;i>=0;--i)maxr[i]=max(maxr[i+1],t[i]);
    reverse(son.begin(),son.end());
    for(i=h[x];i;i=e[i].next){
        y=e[i].to;
        pos=lower_bound(son.begin(),son.end(),dpson[y])-son.begin();pos=son.size()-pos-1;
        if(!pos)dpfa[y]=max(0,maxr[1]-1);
        else if(pos==(int)son.size()-1)dpfa[y]=max(0,maxl[pos-1]);
        dpfa[y]=max(maxl[pos-1],maxr[pos+1]-1); 
    }
    dp[x]=maxl[son.size()-1];for(i=h[x];i;i=e[i].next){y=e[i].to;change_root(y);} 
}

其他细节比如边界什么的需要做了才知道

#include<bits/stdc++.h>
#define N 200005
#define re register
#define INF 0x3f3f3f3f
using namespace std;
struct read{
    char buf[1<<25],*opt;
    read():opt(buf){buf[fread(buf,1,sizeof buf,stdin)]=0;}
    template<typename _int>
    operator _int(){
        _int res=0,flag=1;
        while(*opt<48&&*opt!='-')++opt;
        if(*opt=='-'){flag=-1;++opt;}
        while(*opt>32)res=(res<<1)+(res<<3)+(*opt++)-48;
        return res*flag;
    }
}it;
inline char cmp(re int x,re int y){return y<x;}
struct Edge{int to,next;}e[N<<1];
int n,cnt,h[N],t[N],dpson[N],dpfa[N],maxl[N],maxr[N],fa[N],dp[N],ans=INF,Ans[N];
inline void AddEdge(re int x,re int y){e[++cnt]=(Edge){y,h[x]};h[x]=cnt;}
inline void tree_dp(re int x){
    re int i,y,res=0;re vector<int> son;
    for(i=h[x];i;i=e[i].next){
        y=e[i].to;
        tree_dp(y);
        son.push_back(dpson[y]);
    }
    sort(son.begin(),son.end(),cmp);
    for(i=0;i<(int)son.size();++i)res=max(res,son[i]+i+1);
    dpson[x]=res;
}
inline void change_root(re int x){
    re int i,y,pos;re vector<int> son;
    for(i=h[x];i;i=e[i].next){y=e[i].to;son.push_back(dpson[y]);}if(fa[x])son.push_back(dpfa[x]);
    sort(son.begin(),son.end(),cmp);
    for(i=0;i<(int)son.size();++i)t[i]=son[i]+i+1;
    *maxl=t[0];for(i=1;i<(int)son.size();++i)maxl[i]=max(maxl[i-1],t[i]);
    maxr[son.size()-1]=t[son.size()-1];for(i=son.size()-2;i>=0;--i)maxr[i]=max(maxr[i+1],t[i]);
    reverse(son.begin(),son.end());
    for(i=h[x];i;i=e[i].next){
        y=e[i].to;
        pos=lower_bound(son.begin(),son.end(),dpson[y])-son.begin();pos=son.size()-pos-1;
        if(!pos)dpfa[y]=max(0,maxr[1]-1);
        else if(pos==(int)son.size()-1)dpfa[y]=max(0,maxl[pos-1]);
        else dpfa[y]=max(maxl[pos-1],maxr[pos+1]-1); 
    }
    dp[x]=maxl[son.size()-1];for(i=h[x];i;i=e[i].next){y=e[i].to;change_root(y);} 
}
int main(void){
    n=it;
    re int i;
    for(i=2;i<=n;++i){fa[i]=it;AddEdge(fa[i],i);}
    tree_dp(1);change_root(1);
    for(i=1;i<=n;++i)if(dp[i]<ans){ans=dp[i];Ans[*Ans=1]=i;}else if(ans==dp[i])Ans[++*Ans]=i;
    printf("%d\n",ans+1);
    for(i=1;i<=*Ans;++i)printf("%d ",Ans[i]);
    return 0;
}