P3398 仓鼠找sugar

    • 849通过
    • 2.8K提交
  • 题目提供者 fjzzq2002
  • 评测方式 云端评测
  • 标签 Tarjan 倍增 最近公共祖先,LCA 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小仓鼠的和他的基(mei)友(zi)sugar住在地下洞穴中,每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a)到餐厅(b),而他的基友同时要从他的卧室(c)到图书馆(d)。他们都会走最短路径。现在小仓鼠希望知道,有没有可能在某个地方,可以碰到他的基友?

    小仓鼠那么弱,还要天天被zzq大爷虐,请你快来救救他吧!

    输入输出格式

    输入格式:

    第一行两个正整数n和q,表示这棵树节点的个数和询问的个数。

    接下来n-1行,每行两个正整数u和v,表示节点u到节点v之间有一条边。

    接下来q行,每行四个正整数a、b、c和d,表示节点编号,也就是一次询问,其意义如上。

    输出格式:

    对于每个询问,如果有公共点,输出大写字母“Y”;否则输出“N”。

    输入输出样例

    输入样例#1: 复制
    5 5
    2 5
    4 2
    1 3
    1 4
    5 1 5 1
    2 2 1 4
    4 1 3 4
    3 1 1 5
    3 5 1 4
    输出样例#1: 复制
    Y
    N
    Y
    Y
    Y

    说明

    __本题时限1s,内存限制128M,因新评测机速度较为接近NOIP评测机速度,请注意常数问题带来的影响。__

    20%的数据 n<=200,q<=200

    40%的数据 n<=2000,q<=2000

    70%的数据 n<=50000,q<=50000

    100%的数据 n<=100000,q<=100000

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