2019牛客多校第四场 A meeting 求树的直径

链接:https://ac.nowcoder.com/acm/contest/884/A
来源:牛客网
 

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

A new city has just been built. There're nnn interesting places numbered by positive numbers from 111 to nnn.

In order to save resources, only exactly n−1n-1n−1 roads are built to connect these nnn interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road.

There is one person in each of the places numbered x1,x2…xkx_1,x_2 \ldots x_kx1​,x2​…xk​ and they've decided to meet at one place to have a meal. They wonder what's the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

输入描述:


 

First line two positive integers, n,kn,kn,k - the number of places and persons.

For each the following n−1n-1n−1 lines, there're two integers a,ba,ba,b that stand for a road connecting place aaa and bbb. It's guaranteed that these roads connected all nnn places.

On the following line there're kkk different positive integers x1,x2…xkx_1,x_2 \ldots x_kx1​,x2​…xk​ separated by spaces. These are the numbers of places the persons are at.

输出描述:

A non-negative integer - the minimal time for persons to meet together.

示例1

输入

复制

4 2
1 2
3 1
3 4
2 4

输出

复制

2

说明

They can meet at place 1 or 3.

备注:

1≤n≤1051 \leq n \leq 10^51≤n≤105

题目大意:给你n个点,n-1条边,及m个人所在的点,问这m个人最少需要多少时间才能同时见面,同时走!

题目思路:首先,对这个图进行分析,n个点,exactly(n-1)条边,那么给你就是一颗树,我们先假设给的树是一条直线:

1--->2---->3 ,那么这三个点的人相见的时候的时间就是,(最远的两点距离+1)/2,这是百分百可以确定的。然后我们再看一般情况: 

假设  A C E 我们看其汇聚最短多少时间,我们可以枚举A,C,E 作为起点与其他两个汇聚的时间,我们发现 时间即为两个相聚最远的点相聚的时间,其实也不难理解因为两个最远其余的点一定比这两个早汇合,可以想想直线情况。比如 这个例子 A C 最远所以应该在B 点回合  时间为2

所以现在题目就转换成为了,在一棵树中求k个点中,任意两点距离的最大值,这个最大值有一个概念,叫做树的直径,所谓树的直径就是 树中距离最大的两点之间的距离。树的直径求法:

第一步:任取一个点P为起点,找到与其距离最远的点Q。

第二步:以Q为起点,找到与其最远的点W  Q-W之间的距离即为 树的直径。

证明可以画两条 相交的直线证明,这里不在解释。

还有一个细节:怎么找出k个点组成的树的直径,我们只需要找的时候,只标记在k个点中的点就可以了,其余的点不处理。在k个点中筛选。

具体实现步骤就可以用 两边DFS就可以了,因为这是树复杂度也不可能太大,所以直接深搜:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=2e5+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
int head[maxn];
bool vis[maxn];
bool pos[maxn];
ll dis[maxn];
struct node{
    int e,next;
    ll w;
}edge[maxn];
ll cnt=0;
ll x[maxn];
void addedge(ll u,ll v,ll w)
{
    edge[cnt]=node{v,head[u],w};
    head[u]=cnt++;
    edge[cnt]=node{u,head[v],w};
    head[v]=cnt++;
}
void dfs(ll s)
{
    vis[s]=true;
    for(int i=head[s];i!=-1;i=edge[i].next)
    {
        int e=edge[i].e;
        if(!vis[e])
        {
            dis[e]=dis[s]+1;
            dfs(e);
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n-1;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        addedge(x,y,1);
    }
    for(int i=1;i<=m;i++) {scanf("%lld",&x[i]);pos[x[i]]=true;}
    dfs(x[1]);
    ll z=-1,maxl=-INF;
    for(int i=1;i<=n;i++)
            if(pos[i]&&dis[i]>maxl)
            {
                z=i;
                maxl=dis[i];
            }
    dis[z]=0;
    for(int i=1;i<=n;i++) vis[i]=false;
    maxl=-INF;
    dfs(z);
    for(int i=1;i<=n;i++)
            if(pos[i]&&dis[i]>maxl)
                maxl=dis[i];
    printf("%lld\n",(maxl+1)/2);
    return 0;
}

总结:

1.了解了树的直径,图论的问题和概念还需要进一步扩充。

1.端正心态,继续加油!

全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-29 17:30
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务