[DMOI-R2] 风神瞳(Anemoculus)

题目背景

![](https://gimg2.baidu.com/image_search/src=http%3A%2F%2Fi1.hdslb.com%2Fbfs%2Farchive%2F778e646138c05348a05fc8a5d646201c0be048b0.jpg&refer=http%3A%2F%2Fi1.hdslb.com&app=2002&size=f9999,10000&q=a80&n=0&g=0n&fmt=auto?sec=1665222406&t=01eff8edc99fbecc5e2e94e6e4b8fd01) $$\pmb{\color{Aquamarine}『传说,飞鸟啄去了神像的眼瞳,然后散落到世界各地』}$$ $$\pmb{\color{Aquamarine}『当然了,这只是传说而已』}$$ $$\pmb{\color{Aquamarine}『不过,据说把散失的神瞳献给神像,会有好事发生呢』}$$

题目描述

风起地有一颗大树,它有 $n$ 个节点,以 $1$ 号节点为根。 树上有 $m$ 个风神瞳,第 $i$ 个风神瞳位于节点 $a_i$ 上。 你想要收集这些风神瞳。于是请来了~~在大树旁边摸鱼的~~温迪帮忙。 一开始,你在树的根部的节点,也就是 $1$ 号节点上,每一秒钟,你可以从当前节点走到相邻的节点。或者,你可以请温迪帮忙,他会生成一个风场,你可以通过这个风场直接一次性向上走正好 $k$ 步(我们定义根节点到叶子结点的方向为『上』,即从深度较小的节点到深度较大的节点,换句话说,你可以从当前节点朝着深度更大的节点连续走 $k$ 步)。当你到达某个有风神瞳的节点上时,你就可以收集那个节点的风神瞳,收集不耗费时间。由于从树上跳下来会摔伤,你最后必须回到根节点。现在你有 $q$ 个问题,第 $i$ 个问题是你在 $t_i$ 秒内你最多可以收集到几个风神瞳。

输入输出格式

输入格式


第一行四个正整数 $n,m,k,q$,含义如题目描述中所述。 接下来 $n - 1$ 行,每行两个正整数 $u,v$,表示结点 $u$ 和结点 $v$ 是相邻的。 接下来一行 $m$ 个互不相同的正整数,第 $i$ 个数表示 $a_i$,含义如题目描述中所述。 接下来 $q$ 行,其中第 $i$ 行有一个正整数 $t_i$,含义如题目描述中所述。

输出格式


对于 $q$ 次询问,每次询问输出一行,表示最多可以收集到几个风神瞳。

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
1
2
2
3

输入样例 #2

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

输出样例 #2

0
1
2
2
3
3

说明

--- ### 样例解释 #### 样例一 ![](https://cdn.luogu.com.cn/upload/image_hosting/mz5mcnuo.png) 如图,其中加粗的点是有风神瞳的点。温迪~~很懒~~有事所以不准备帮你。 #### 样例二 这个样例除了温迪能让你一次性向上走两步和样例一没有区别。 --- ### 数据范围 本题采用捆绑测试。 对于 $5\%$ 的数据,$m = 10$。 对于另外 $15\%$ 的数据,$m = 17$。 对于另外 $20\%$ 的数据,$k=1$。 对于 $100\%$ 的数据,$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)$,其中 $dep$ 表示树的深度,定义根节点的深度为 $1$。