[BalticOI 2015] File Paths

题目描述

一个文件 $\tt file$ 都需要在一个包含很多文件 $\tt dir1,dir2,\cdots,dirj$ 的目录中,这个文件的 absolute file path 为 $\tt/dir1/dir2/\cdots/dirj/file$,根目录用 $\tt /$ 表示,每一个放在根目录下的文件的 absolute file path 的形式为 $\tt /file$。 符号链接指向一个已被命名的目录,可以看作一个快捷方式,他可以放置在任意目录下,注意,符号链接不能指向文件。比如,我们在 $\tt /$ 下放一个指向 $\tt /$ 的符号链接 $\tt hello$,那么,$\tt /dir/file$,$\tt /hello/dir/file$,$\tt /hello/hello/dir/dile$ 都指向同一个文件 $\tt file$。另比如,我们在 $\tt /dir$ 下放一个指向 $\tt /$ 的符号链接 $\tt hi$,那么,$\tt /dir/file$,$\tt /dir/hi/dir/file$,$\tt /dir/hi/dir/hi/dir/file$ 都指向同一个文件 $\tt file$。符号链接指向上一层,下一层,甚至同层都可以,但是不允许 $\tt ./$,$\tt ../$,$\tt //$ 之类的操作。 现在想问,是否能通过引入一个长为 $s$ 的符号链接使得找到一个文件的 absolute file path 长度恰好为 $k$?

输入输出格式

输入格式


第一行三个整数 $n,m,k$ 代表除根目录之外的目录数,文件数和要求等于的路径长度。 第二行一个整数 $s$ 代表符号链接长。 接下来 $n$ 行每行两个整数 $p_i,l_i$ 描述一个目录,这个目录编号为 $l_i$,父目录编号为 $p_i$。 接下来 $m$ 行每行两个整数 $p_j,l_j$,描述一个文件,这个文件的长度为 $l_j$,父目录编号为 $p_j$。

输出格式


$m$ 行每行一个字符串代表是否能通过引入一个长为 $s$ 的符号链接使得找到编号为 $j$ 的文件的 absolute file path 长度恰好为 $k$,如果是的话输出 $\tt YES$,否则输出 $\tt NO$。

输入输出样例

输入样例 #1

2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

输出样例 #1

YES
YES
YES
NO

说明

#### 样例 1 解释 假设符号链接名字为 $\tt LL$,目录名字为 $\tt a$,$\tt bbbbb$,文件名字为 $\tt ccccccccccccc$,$\tt dddddddddd$,$\tt eee$,$\tt fffffff$,根目录下包含目录 $\tt a$ 和文件 $\tt fffffff$,目录 $\tt a$ 下包含目录 $\tt bbbbb$ 和文件 $\tt eee$,目录 $\tt bbbbb$ 包含文件 $\tt ccccccccccccc$ 和 $\tt dddddddddd$。下面是形象化的表述: ```plain / |-- a | |-- bbbbb | | |-- ccccccccccccc | | +-- dddddddddd | +-- eeee +-- fffffff ``` - 对于第 $1$ 个文件,满足条件的路径为 $\tt /a/bbbbb/ccccccccccccc$。 - 对于第 $2$ 个文件,满足条件的路径为 $\tt /a/LL/bbbbb/dddddddddd$。 - 对于第 $3$ 个文件,满足条件的路径为 $\tt /a/LL/a/LL/a/LL/a/eeee$。 - 对于第 $4$ 个文件,无满足条件的路径。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1(33 pts):$n,m \le 500$。 - Subtask 2(33 pts):$n,m \le 3 \times 10^3$,符号链接最多被调用一次。 - Subtask 3(34 pts):无特殊限制。 对于 $100\%$ 的数据,$1 \le k,s \le 10^6$,$1\le m,n\le 3\times 10^3$。 #### 说明 翻译自 [BalticOI 2015 Day2 A File Paths](https://boi.cses.fi/files/boi2015_day2.pdf)。