未知：爱心蜗牛——题解

178 阅读 0 评论 118 点赞

我是靠谱客的博主孝顺夏天，最近开发中收集的这篇文章主要介绍未知：爱心蜗牛——题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近做了好多题，会筛选一下然后发一些好的题。
比如这道？
————————————————————
“路由器，你看，我又学会了新的算法，树上dp，怎么样？”
勇者趾高气昂看了看路由器。
“……那你还是去看一本书吧，《c++，从算法到暴力》（虚构，雷同是巧合）
————————————————————
【题目描述】
猫猫把嘴伸进池子里，正准备“吸”鱼吃，却听到门铃响了。猫猫擦了擦脸上的水，打开门
一看，那人正是她的好朋友——川川。
川川手里拿着一辆玩具汽车，对猫猫说：“这是我的新汽车！”接着，伴随一阵塑料叩击声，
玩具汽车的车门竟开了，一只蜗牛慢慢吞吞爬了出来。
“哇！这么大的蜗牛……”猫猫惊讶道。
“这是我的宠物蜗牛，他叫点点。”川川介绍道。
“把他送给我好吗？”猫猫央求道。
“可以让他陪你几天，但是不能送给你……”
点点沿着川川的身体，爬到了地上，又移到了猫猫的池子旁边，只听见猫猫向川川介绍她
的“创意吃鱼法”，心里不禁起了一丝凉意：“这个女生太毒了……吃鱼前还要玩鱼……”转眼一看，
池中的鱼依旧畅快地游来游去。
“或许这些鱼听不懂猫语吧……好在我会一点儿猫语，也会一点鱼语……阿弥陀佛，善哉善哉。
我还是救救这些鱼吧……”点点自言自语，一边费力地移动着身躯。他认识到——单凭自己的力
量，把猫猫的阴谋告诉每一条鱼，似乎不太可能——自己底盘太低，走不快，看来只得想其他
办法来传达信息。一翻认真思考之后，点点想到，如果把猫猫的计划告诉其中一条鱼，再让鱼
们互相传达消息，那么在相对较短的时间内，每条鱼都会得知猫猫的计划。
鱼们的社会等级森严，除了国王菜鱼之外，每条鱼均有且只有一个直接上级，菜鱼则没有
上级。如果A 是B 的上级，B 是C 的上级，那么A 就是C 的上级。
绝对不会出现这样两条鱼A、B：A 是B 的上级，B 也是A 的上级。
最开始的时刻是0，点点要做的，就只是用1 单位的时间把猫猫的阴谋告诉某一条“信息源
鱼”，让鱼们自行散布消息。在任意一个时间单位中，任何一条已经接到通知的鱼，都可以把
消息告诉他的一个直接上级或者直接下属。
现在，点点想知道：
1.到底需要多长时间，消息才能传遍池子里的鱼？
2.使消息传递过程消耗的时间最短，可供选择的“信息源鱼”有那些？
【输入】)
第一行有一个数N（N≤1000），表示池中的鱼数，池鱼按照1 到n 编上了号码，国王菜鱼
的标号是1。
第二行到第N 行（共N-1 行），每一行一个数，第I 行的数表示鱼I 的直接上级的标号。
【输出】
第一行有一个数，表示最后一条鱼接到通知的最早时间。
第二行有若干个数，表示可供选择的鱼F 的标号，按照标号从小到大的顺序输出，中间用
空格分开。
【样例输入】
8
1
1
3
4
4
4
3

——————————————————
树上dp？正解的确是这样的。
然而……路由器不是这么写的。
（虽然思路都是完全一样的，如果想知道正解就网上搜吧，貌似这道题有年头了）
//p.s.路由器的代码因为不是dp所以很慢，但是能过。

这题不要考虑上下属，那个国王也一点也没有用。
我们把它看成无根树即可。
枚举每个鱼作为根节点dfs。
t为将其与其的子树全部通知到所需要的时间。
叶子节点的时间t明显为1。
往上的节点的时间就为其所有子树的根的最大时间。

当然我们这样就会发现问题。
比如说1个点连了10000个点。
那么这个点的时间就是10000而不是1.
所以我们需要对拥有相同时间的子树进行“合并”。
我们发现两个时间为2的子树相当于一个时间为3的子树。
……（又是找规律）
所以发现n个时间为k的子树相当于一个时间为k-n+1的子树。
对于新合并的子树我们再重新求一遍max即可。
过程就桶排，时间不会超过1000 。
然而还有问题……正如上面说的，我们的速度不是特别的快。
所以我们在合并子树的时候事先处理好时间下限和上限就好了。
//如果想测一下速度的话，推荐造一个n=1000的链状树。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct{
    int to;
    int next;
}edge[2001];
int cnt=0,head[1001]={0};
void add(int u,int v){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
    return;
}
int t[1001]={0};
bool vis[1001]={0};
int mint=2147483647;
int l=0;
int a[1001];
int dfn[1001][1001];
void dfs(int u){
    int maxn=0;
    int minn=2147483647;
    vis[u]=1;
    int ok=0;
    for(int i=head[u];i!=0;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]==0){
            ok=1;
            dfs(v);
            dfn[u][t[v]]++;
            maxn=max(maxn,t[v]);
            minn=min(minn,t[v]);
        }
    }
    if(ok==0){
        t[u]=1;
        return;
    }
    for(int i=minn;i<=maxn;i++){
        if(dfn[u][i]>=2){
            dfn[u][i+dfn[u][i]-1]++;
            maxn=max(maxn,i+dfn[u][i]-1);
            dfn[u][i]=0;
        }
    }
    t[u]=maxn+1;
    return;
}
int main(){
    freopen("badnews.in","r",stdin);
    freopen("badnews.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int ha;
        scanf("%d",&ha);
        add(ha,i);add(i,ha);
    }
    for(int i=1;i<=n;i++){
        memset(t,0,sizeof(t));
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        dfs(i);
        if(mint>t[i]){
            mint=t[i];
            l=1;
            a[l]=i;
        }else if(mint==t[i]){
            l++;
            a[l]=i;
        }
    }
    printf("%dn",mint);
    for(int i=1;i<=l;i++){
        printf("%d ",a[i]);
    }
    return 0;
}