首页 > 其他 > 详细

1773:消息传递

时间:2020-01-19 00:58:35      阅读:76      评论:0      收藏:0      [点我收藏+]

标签:scanf   一道   str   %d   inline   open   

1773:消息传递

时间限制: 1000 ms 内存限制: 262144 KB

【题目描述】
H国的社会等级森严,除了国王之外,每个人均有且只有一个直接上级,当然国王没有上级。如果A是B的上级,B是C的上级,那么A就是C的上级。绝对不会出现这样的关系:A是B的上级,B也是A的上级。

最开始的时刻是0,你要做的就是用1单位的时间把一个消息告诉某一个人,让他们自行散布消息。在任意一个时间单位中,任何一个已经接到消息的人,都可以把消息告诉他的一个直接上级或者直接下属。

现在,你想知道:

①到底需要多长时间,消息才能传遍整个H国的所有人?

②要使消息在传递过程中消耗的时间最短,可供选择的人有哪些?

【输入】
第一行为一个整数N,表示H国人的总数,假如人按照1到n编上了号码,国王的编号是1。

第二行到第N行(共N−1行),每一行一个整数,第i行的整数表示编号为i的人直接上级的编号。

【输出】
输出共计两行:

第一行为一个整数,表示最后一个人接到消息的最早时间。

第二行有若干个数,表示可供选择人的编号,按照编号从小到大的顺序输出,中间用一个空格隔开。

【输入样例】
4
1
1
1
【输出样例】
4
1 2 3 4

【输入样例2】

8
1
1
3
4
4
4
3
【输出样例2】

5
3 4 5 6 7
【数据规模与约定】

对于20%的数据,N≤3000。

对于50%的数据,N≤20000。

对于100%的数据,N≤200000。

 【题解】

实际上是一道水题。

可以很方便的求出以u为根传递完它的子树的代价f[u]。

考虑如何求出传完它父亲及其上方点的代价。

使用换根dp。令g[u]表示去掉u及其子树并以u的父亲为根的全部代价。

将所有儿子的f与自己的g排序后即可求出所有儿子的g。

每个点的答案就很好计算了。

代码如下:

技术分享图片
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int f[N],g[N],n,last[N],size,pre[N],sub[N],ans[N],ans1=999999999,daan[N],ans2;
struct pigu
{
    int dao,ne;
}a[N];
pair <int,int> b[N];
inline void lingjiebiao(int x,int y)
{
    a[++size].dao=y;
    a[size].ne=last[x];
    last[x]=size;
}
inline void dfs1(int now)
{
    for(int i=last[now];i;i=a[i].ne)
        dfs1(a[i].dao);
    int cnt=0;
    for(int i=last[now];i;i=a[i].ne)
        b[++cnt]=make_pair(f[a[i].dao],a[i].dao);
    sort(b+1,b+cnt+1);
    for(int i=1;i<=cnt;i++)
        f[now]=max(f[now],b[i].first+cnt-i+1);
}
inline void dfs2(int now)
{
    int cnt=0;
    for(int i=last[now];i;i=a[i].ne)
    {
        b[++cnt]=make_pair(f[a[i].dao],a[i].dao);
    }
    if(now!=1) b[++cnt]=make_pair(g[now],-1);
    if(cnt==1&&now==1) g[now]=1; 
    sort(b+1,b+cnt+1);
    for(int i=1;i<=cnt;i++) ans[now]=max(b[i].first+cnt-i+1,ans[now]);pre[0]=sub[cnt+1]=-1;
    for(int i=1;i<=cnt;i++) pre[i]=max(pre[i-1],b[i].first+cnt-i);
    for(int i=cnt;i>=2;i--) sub[i]=max(sub[i+1],b[i].first+cnt-i+1);
    for(int i=1;i<=cnt;i++)
    {
        if(b[i].second!=-1)
            g[b[i].second]=max(pre[i-1],sub[i+1]);
    }
    for(int i=last[now];i;i=a[i].ne) dfs2(a[i].dao);
}
int main()
{
    scanf("%d",&n);
    for(int i=2,x;i<=n;i++)
    {
        scanf("%d",&x);
        lingjiebiao(x,i);
    }
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=n;i++) 
        if(ans1>ans[i]) ans1=ans[i],daan[ans2=1]=i;
        else if(ans1==ans[i]) daan[++ans2]=i;
    cout<<ans1+1<<"\n";
    for(int i=1;i<=ans2;i++) cout<<daan[i]<<" ";
    return 0;
}
View Code

1773:消息传递

标签:scanf   一道   str   %d   inline   open   

原文:https://www.cnblogs.com/betablewaloot/p/12210779.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号