P6843 [BalticOI 2015] File Paths

A file $\tt file$ must be located in a directory that contains many directories $\tt dir1,dir2,\cdots,dirj$. The absolute file path of this file is $\tt/dir1/dir2/\cdots/dirj/file$. The root directory is denoted by $\tt /$. For a file placed directly under the root directory, its absolute file path has the form $\tt /file$. A symbolic link points to a named directory and can be seen as a shortcut. It can be placed in any directory. Note that a symbolic link cannot point to a file. For example, if we place under $\tt /$ a symbolic link $\tt hello$ that points to $\tt /$, then $\tt /dir/file$, $\tt /hello/dir/file$, and $\tt /hello/hello/dir/dile$ all refer to the same file $\tt file$. As another example, if we place under $\tt /dir$ a symbolic link $\tt hi$ that points to $\tt /$, then $\tt /dir/file$, $\tt /dir/hi/dir/file$, and $\tt /dir/hi/dir/hi/dir/file$ all refer to the same file $\tt file$. A symbolic link may point to the parent directory, a child directory, or even a directory on the same level, but operations such as $\tt ./$, $\tt ../$, and $\tt //$ are not allowed. Now the question is: is it possible, by introducing one symbolic link of length $s$, to make it possible to find an absolute file path of some file whose length is exactly $k$?

The first line contains three integers $n,m,k$, representing the number of directories (excluding the root directory), the number of files, and the required path length $k$. The second line contains an integer $s$, representing the length of the symbolic link. The next $n$ lines each contain two integers $p_i,l_i$, describing a directory: this directory has ID $l_i$, and its parent directory has ID $p_i$. The next $m$ lines each contain two integers $p_j,l_j$, describing a file: this file has length $l_j$, and its parent directory has ID $p_j$.

Output $m$ lines. Each line is a string indicating whether, by introducing one symbolic link of length $s$, it is possible to find an absolute file path of length exactly $k$ for file $j$. If yes, output $\tt YES$; otherwise, output $\tt NO$.

#### Sample 1 Explanation Assume the symbolic link name is $\tt LL$, the directory names are $\tt a$ and $\tt bbbbb$, and the file names are $\tt ccccccccccccc$, $\tt dddddddddd$, $\tt eee$, and $\tt fffffff$. The root directory contains directory $\tt a$ and file $\tt fffffff$. Directory $\tt a$ contains directory $\tt bbbbb$ and file $\tt eee$. Directory $\tt bbbbb$ contains files $\tt ccccccccccccc$ and $\tt dddddddddd$. A visual representation is: ```plain / |-- a | |-- bbbbb | | |-- ccccccccccccc | | +-- dddddddddd | +-- eeee +-- fffffff ``` - For file $1$, a path that satisfies the condition is $\tt /a/bbbbb/ccccccccccccc$. - For file $2$, a path that satisfies the condition is $\tt /a/LL/bbbbb/dddddddddd$. - For file $3$, a path that satisfies the condition is $\tt /a/LL/a/LL/a/LL/a/eeee$. - For file $4$, no path satisfies the condition. #### Constraints and Notes **This problem uses bundled tests.** - Subtask 1 (33 pts): $n,m \le 500$. - Subtask 2 (33 pts): $n,m \le 3 \times 10^3$, and the symbolic link is used at most once. - Subtask 3 (34 pts): no special restrictions. For $100\%$ of the testdata, $1 \le k,s \le 10^6$, and $1 \le m,n \le 3\times 10^3$. #### Notes Translated from [BalticOI 2015 Day2 A File Paths](https://boi.cses.fi/files/boi2015_day2.pdf)。 Translated by ChatGPT 5