TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3714
  • 题目
  • P3714到不了
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 时限1000ms
    问题描述

    Description

    wy和wjk是好朋友。

    今天他们在一起聊天,突然聊到了以前一起唱过的《到不了》。

    “说到到不了,我给你讲一个故事吧。”

    “嗯?”

    “从前,神和凡人相爱了,愤怒的神王把他们关进了一个迷宫里,迷宫是由许多棵有根树组成的。神王每次把两个人扔进迷宫里面,两个相邻节点的距离为1,两人的每一步都只能从儿子走到父亲,不能从父亲走到儿子,他们约定,走到同一个节点相见,由于在迷宫里面行走十分消耗体力,他们决定找出那个使得他们走的总路程最少的节点,他们当然会算出那个节点了,可是神王有时候会把两棵有根树合并为一棵,这下就麻烦了。。。”

    “唔。。。”

    [已经了解树,森林的相关概念的同学请跳过下面一段]

    树:由n个点,n-1条边组成的无向连通图。

    父亲/儿子:把树的边距离定义为1,root是树的根,对于一棵树里面相邻的两个点u,v,到root的距离近的那个点是父亲,到root距离远的那个点是儿子

    森林:由若干棵树组成的图

    [简化版题目描述]

    维护一个森林,支持连边操作和查询两点LCA操作

    输入格式

    第一行一个整数N,M,代表森林里的节点总数和有根树的数目。

    第二行M个整数,第i个整数ri代表第i棵有根树的根是编号为ri的节点

    第三行一个整数E=N-M,代表边的数量

    接下来E行,每行两个整数u,v表示u和v相邻

    接下来一行一个整数Q,表示Q个事件发生了

    接下来Q行,每行若干个整数,表示一个事件

    如果第一个数op=1,接下来两个整数u,v,代表神王把u号节点所在的树和v号节点所在的树合并到一起(即u到v连了一条边),新的根为原来u号节点所在的树的根(如果u,v已经联通,忽略这个事件)。

    如果第一个数op=2,接下来两个整数u,v,代表一次询问,当一个人在u号节点,一个人在v号节点,询问他们找到的那个节点的编号

    输出格式

    对于每一个询问(op=2的操作),输出一行一个整数,代表节点编号,如果u,v不联通,输出"orzorz"。

    样例输入 1

    2 2
    1 2
    0
    2
    1 1 2
    2 1 2

    样例输出 1

    1

    样例输入 2

    2 2
    1 2
    0
    2
    1 2 1
    2 1 2

    样例输出 2

    2

    提示

    对于30%的数据 1 ≤ N ≤ 1000 1 ≤ Q ≤ 1000

    对于100%的数据 1 ≤ N ≤ 100000 1 ≤ Q ≤ 100000


    来源  ShadowIterator原创