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

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

题目描述

一方通行出事了。

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

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

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

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

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

输入格式

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

接下来 N1N-1 行,每行两个整数 u,vu, v,表示 uu 号个体和 vv 号个体之间有一条边。

接下来 MM 行,每行两个整数 a,typea, \mathrm{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

见附加文件。

数据范围与提示

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

子任务编号 分值 N,MN,M 特殊性质
1 1515 20\leq 20 -
2 1515 1000\leq 1000 -
3 3535 10000\leq 10000 -
4 1010 50000\leq 50000 保证输入是一条链
5 2525 50000\leq 50000 -