#571. 「LibreOJ Round #11」Misaka Network 与 Accelerator

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tqyaaaaang

题目描述

一方通行出事了。

现在计划用 Misaka Network 的来弥补一方通行的计算力。Misaka Network 由 NNN 个个体组成,个体之间由 N−1N-1N1 条边连接,边连接的两个个体可以通过脑电波互通信息。Misaka Network 的构造保证任意个体能够直接或间接通信,即构成一棵树。

现在要让一方通行接入这个网络,一方通行可以选择一部分个体,并与这些个体之间通信。但是出于稳定性要求,有一些限制条件,每个条件给出 a,typea, typea,type

  • type=0type = 0type=0:如果一方通行不和 aaa 号个体直接通信,那么他不能和任何距离 aaa[L,R][L,R][L,R] 之间的个体直接通信
  • type=1type = 1type=1:如果一方通行不和 aaa 号个体直接通信,那么他必须和所有距离 aaa[L,R][L,R][L,R] 之间的个体直接通信
  • type=2type = 2type=2:如果一方通行决定和 aaa 号个体直接通信,那么他不能和任何距离 aaa[L,R][L,R][L,R] 之间的个体直接通信
  • type=3type = 3type=3:如果一方通行决定和 aaa 号个体直接通信,那么他必须和所有距离 aaa[L,R][L,R][L,R] 之间的个体直接通信

其中 L,RL, RL,R 都是 Misaka Network 的参数,各个限制都是一样的。

如果一种通信方案能满足所有条件,那么一方通行就能成功接入网络。一方通行想知道是否能够成功接入网络。

输入格式

第一行四个整数 N,M,L,RN, M, L, RN,M,L,R

接下来 N−1N-1N1 行,每行两个整数 u,vu, vu,v,表示 uuu 号个体和 vvv 号个体之间有一条边。

接下来 MMM 行,每行两个整数 a,typea, typea,type,表示一组限制条件。

输出格式

一行一个字符串 YES 或者 NO。若为 NO,表示一方通行无论如何都无法接入网络,否则为 YES

样例

样例输入 1

3 2 1 2
1 2
1 3
2 1
3 1

样例输出 1

YES

样例解释 1

一种可行的方案是和所有个体都建立直接通信

样例输入 2

3 4 1 2
1 2
1 3
1 0
1 1
1 2
1 3

样例输出 2

NO

样例 3

见附加文件。

数据范围与提示

对于所有数据 1≤N,M≤500001 \leq N,M \leq 500001N,M500001≤L≤R≤500001 \leq L \leq R \leq 500001LR50000

子任务编号 分值 N,MN,MN,M 特殊性质
1 151515 ≤20\leq 2020 -
2 151515 ≤1000\leq 10001000 -
3 353535 ≤10000\leq 1000010000 -
4 101010 ≤50000\leq 5000050000 保证输入是一条链
5 252525 ≤50000\leq 5000050000 -