P2416 泡芙

    • 30通过
    • 397提交
  • 题目提供者 Scarlet 管理员
  • 评测方式 云端评测
  • 标签 图论 树形结构 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 256MB

题解

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

    推荐的相关题目 显示

    题目背景

    此题空间限制256M,保证系统栈空间与内存限制大小相同

    此题空间限制256M,保证系统栈空间与内存限制大小相同

    此题空间限制256M,保证系统栈空间与内存限制大小相同

    题目描述

    火星猫经过一番努力终于到达了冥王星。他发现冥王星有 N 座城市,M 条无向边。火星猫准备出发去找冥王兔,他听说有若干泡芙掉落在一些边上,他准备采集一些去送给冥王兔。但是火星猫的火星光环和冥王星相生相克,当火星猫走过一条路之后,这条路就不能再走了。如果冥王兔吃不到泡芙,他们就不能嘿嘿嘿了。所以告诉你火星猫和冥王兔的位置,请问冥王兔能不能吃到泡芙。

    输入输出格式

    输入格式:

    第一行 N,M 表示点数和边数。

    接下来 M 行每行 X,Y,Z 表示 X 到 Y 有一条无向边,Z=1 表示有泡芙,Z=0 表示没有

    接下来一行是 Q,表示有 Q 组询问。

    每行 S,T 表示火星猫和冥王兔的位置。

    输出格式:

    对于每组询问输出 YES 或 NO

    输入输出样例

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

    说明

    no    N<=    M<=    Q<=    备注
    3-4    1000    N-1    50000    保证图是一棵树
    5-8    300000    N-1    300000    
    9-10    20    50    5    无
    11-14    1000    5000    50000    
    15-20    300000    300000    300000    

    保证图联通

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