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

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

题目描述

一方通行出事了。

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

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

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

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

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

输入格式

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

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

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

见附加文件。

数据范围与提示

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

子任务编号 分值 N,M 特殊性质
1 15 \leq 20 -
2 \leq 1000
3 35 \leq 10000
4 10 \leq 50000 保证输入是一条链
5 25 -