P2195 HXY造公园

    • 218通过
    • 941提交
  • 题目提供者 caozy623
  • 评测方式 云端评测
  • 标签 图论 并查集 广度优先搜索,BFS 搜索 树的直径
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    现在有一个现成的公园,有n个休息点和m条双向边连接两个休息点。众所周知,HXY是一个SXBK的强迫症患者,所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作:

    1、对某个休息点x,查询公园中可以与个点互相到达的休息点组成的路径中的最长路径

    2、对于两个休息点x、y,如果x,y已经可以互相到达则忽略此次操作。否则,在x可到达的所有休息点和y可到达的所有休息点(包括x,y自身)分别选择一个休息点,然后在这两个休息点之间连一条边,并且这个选择应该满足对于连接后的公园,x和y所在的区域(即x,y可达到的所有休息点和边组成的集合)中的最长路径的长度最小。

    HXY打算进行q个操作,请你回答她的对于公园情况的询问(操作1)或者执行她的操作(操作2)。

    注:所有边的长度皆为1。保证不存在环。最长路径定义为:对于点v1,v2......vk,如果对于其中任意的vi和vi+1(1<=i<=k-1),都有边相连接,那么vj(1<=j<=k)所在区域的最长路径就是k-1。

    输入输出格式

    输入格式:

    第一行,三个正整数,分别为n,m,q。

    接下来的m行,每一行有两个正整数xi,yi,表示xi和yi有一条双向边相连。

    再接下来的q行,每一行表示一个操作。

    若该行第一个数为1,则表示操作1,之后还有一个正整数xi,表示要查询的休息点。

    若该行第一个数为2,则表示操作2,之后还有两个正整数xi,yi,表示需要执行操作的两个休息点。

    输出格式:

    输出行数为操作1的个数。

    每行输出对于操作1询问的回答。

    输入输出样例

    输入样例#1: 复制
    6 0 6
    2 1 2
    2 3 4
    2 5 6
    2 3 2
    2 5 3
    1 1
    输出样例#1: 复制
    4
    

    说明

    数据范围:

    对于10%的数据,只存在操作1。

    对于30%的数据,1<=m<n<=20,1<=q<=5。

    对于60%的数据,1<=m<n<=2000,1<=q<=1000。

    对于100%的数据,1<=m<n<=3*10^5,1<=q<=3*10^5。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。