{"problem":{"name":"[DMOI-R2] 风神瞳（Anemoculus）","description":{"content":"风起地有一颗大树，它有 $n$ 个节点，以 $1$ 号节点为根。 树上有 $m$ 个风神瞳，第 $i$ 个风神瞳位于节点 $a_i$ 上。 你想要收集这些风神瞳。于是请来了~~在大树旁边摸鱼的~~温迪帮忙。 一开始，你在树的根部的节点，也就是 $1$ 号节点上，每一秒钟，你可以从当前节点走到相邻的节点。或者，你可以请温迪帮忙，他会生成一个风场，你可以通过这个风场直接一次性向上走正好 $k$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":350,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8917"},"statements":[{"statement_type":"Markdown","content":"风起地有一颗大树，它有 $n$ 个节点，以 $1$ 号节点为根。\n\n树上有 $m$ 个风神瞳，第 $i$ 个风神瞳位于节点 $a_i$ 上。\n\n你想要收集这些风神瞳。于是请来了~~在大树旁边摸鱼的~~温迪帮忙。\n\n一开始，你在树的根部的节点，也就是 $1$ 号节点上，每一秒钟，你可以从当前节点走到相邻的节点。或者，你可以请温迪帮忙，他会生成一个风场，你可以通过这个风场直接一次性向上走正好 $k$ 步（我们定义根节点到叶子结点的方向为『上』，即从深度较小的节点到深度较大的节点，换句话说，你可以从当前节点朝着深度更大的节点连续走 $k$ 步）。当你到达某个有风神瞳的节点上时，你就可以收集那个节点的风神瞳，收集不耗费时间。由于从树上跳下来会摔伤，你最后必须回到根节点。现在你有 $q$ 个问题，第 $i$ 个问题是你在 $t_i$ 秒内你最多可以收集到几个风神瞳。\n\n## Input\n\n第一行四个正整数 $n,m,k,q$，含义如题目描述中所述。\n\n接下来 $n - 1$ 行，每行两个正整数 $u,v$，表示结点 $u$ 和结点 $v$ 是相邻的。\n\n接下来一行 $m$ 个互不相同的正整数，第 $i$ 个数表示 $a_i$，含义如题目描述中所述。\n\n接下来 $q$ 行，其中第 $i$ 行有一个正整数 $t_i$，含义如题目描述中所述。\n\n## Output\n\n对于 $q$ 次询问，每次询问输出一行，表示最多可以收集到几个风神瞳。\n\n[samples]\n\n## Background\n\n![](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)\n\n$$\\pmb{\\color{Aquamarine}『传说，飞鸟啄去了神像的眼瞳，然后散落到世界各地』}$$\n\n$$\\pmb{\\color{Aquamarine}『当然了，这只是传说而已』}$$\n\n$$\\pmb{\\color{Aquamarine}『不过，据说把散失的神瞳献给神像，会有好事发生呢』}$$\n\n## Note\n\n---\n### 样例解释\n#### 样例一\n![](https://cdn.luogu.com.cn/upload/image_hosting/mz5mcnuo.png)\n\n如图，其中加粗的点是有风神瞳的点。温迪~~很懒~~有事所以不准备帮你。\n#### 样例二\n这个样例除了温迪能让你一次性向上走两步和样例一没有区别。\n\n---\n### 数据范围\n\n本题采用捆绑测试。\n\n对于 $5\\%$ 的数据，$m = 10$。\n\n对于另外 $15\\%$ 的数据，$m = 17$。\n\n对于另外 $20\\%$ 的数据，$k=1$。\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8917","tags":["O2优化","树形 DP"],"sample_group":[["8 3 1 6\n1 2\n1 3\n1 6\n2 4\n2 5\n3 7\n3 8\n6 7 8\n1\n3\n5\n6\n7\n8","0\n1\n1\n2\n2\n3"],["8 3 2 6\n1 2\n1 3\n1 6\n2 4\n2 5\n3 7\n3 8\n6 7 8\n1\n3\n5\n6\n7\n8","0\n1\n2\n2\n3\n3"]],"created_at":"2026-03-03 11:09:25"}}