Background

$$\pmb{\color{Aquamarine}\text{『Legend says that birds pecked out the eyes of the statue, and they were scattered across the world』}}$$$$\pmb{\color{Aquamarine}\text{『Of course, it is just a legend』}}$$$$\pmb{\color{Aquamarine}\text{『But it is said that if you offer the lost “divine eyes” to the statue, good things will happen』}}$$

Problem Description

In Windrise, there is a big tree with $n$ nodes, rooted at node $1$.

There are $m$ Anemoculi on the tree. The $i$-th Anemoculus is located at node $a_i$.

You want to collect these Anemoculi, so you ask Venti for help (who is slacking off by the big tree).

At the beginning, you are at the root of the tree, i.e. node $1$. Each second, you can move from the current node to an adjacent node. Alternatively, you can ask Venti for help: he will create a wind current, and you can use it to move upward exactly $k$ steps in one go. (We define the direction from the root to the leaves as “up”, i.e. from a node with smaller depth to a node with larger depth. In other words, you can move from the current node toward greater depth for $k$ consecutive steps.) When you reach a node that has an Anemoculus, you can collect the Anemoculus at that node, and collecting takes no time. Since you would get hurt if you jump down from the tree, you must return to the root in the end. Now you have $q$ queries. For the $i$-th query, you are asked: within $t_i$ seconds, what is the maximum number of Anemoculi you can collect?

Input Format

The first line contains four positive integers $n,m,k,q$, with meanings as described above.

The next $n - 1$ lines each contain two positive integers $u,v$, indicating that nodes $u$ and $v$ are adjacent.

The next line contains $m$ pairwise distinct positive integers. The $i$-th number is $a_i$, with meaning as described above.

The next $q$ lines each contain one positive integer $t_i$, with meaning as described above.

Output Format

For each of the $q$ queries, output one line, indicating the maximum number of Anemoculi that can be collected.

8 3 1 6
1 2
1 3
1 6
2 4
2 5
3 7
3 8
6 7 8
1
3
5
6
7
8

0
1
1
2
2
3

8 3 2 6
1 2
1 3
1 6
2 4
2 5
3 7
3 8
6 7 8
1
3
5
6
7
8

0
1
2
2
3
3

Hint

---

Sample Explanation

Sample 1

As shown, the bold nodes are those with Anemoculi. Venti is very lazy is busy and will not help you.

Sample 2

This sample is the same as Sample 1, except that Venti allows you to move upward by two steps at once.

---

Constraints

This problem uses bundled testdata.

For $5\%$ of the testdata, $m = 10$.

For another $15\%$ of the testdata, $m = 17$.

For another $20\%$ of the testdata, $k = 1$.

For $100\%$ of the testdata, $n \leq 2000$, $m \leq 500$, $q \le 1000$, $1\leq t_i \leq 2\times n$, $1\le a_i,u,v \le n$, $1 \leq k\le \min(dep-1,100)$, where $dep$ is the depth of the tree, and the depth of the root is defined as $1$.

Translated by ChatGPT 5