题目描述

哥萨克胡子最近来到了一个非常有趣的国家。该国有 $n$ 个城市，其中编号为 $1$ 的城市是国家的 首都。这些城市之间恰好有 $n - 1$ 条道路，第 $i$ 条道路连接城市 $v_i$ 和 $u_i$。同时已知，从任何一个城市都可以通过仅在这些道路上移动而到达任何其他城市。

每个城市都是某个区域的中心。区域 被定义为所有顶点 $v$ 的集合，使得从首都到 $v$ 的任何路径都必须经过该区域的中心（一个城市可以属于多个区域）。

编号为 $i$ 的城市恰好居住着 $a_i$ 位公民，并且所有 $a_i$ 的值 互不相同。胡子得知，国家政$$府有权执行 “人口交换” 操作——选择一对城市 $x$ 和 $y$，并将城市 $x$ 的 所有 居民迁往城市 $y$，同时将城市 $y$ 的 所有 居民迁往城市 $x$。我们的哥萨克最多可以请求政$$府执行 $k$ 次 “人口交换”。进行 “人口交换” 时所选的城市对也由胡子指定。

每天，哥萨克都会选择一个数字作为他当天的“最喜欢的数字”。如果 $x$ 是胡子最喜欢的数字，那么他认为一个区域是 “优美区域”，当且仅当可以通过不超过 $k$ 次 “人口交换” 操作，使得该区域内各城市人口数量的 中位数 等于 $x$。也就是说，如果将区域内城市的人口数量按 升序 排列，那么所得序列中间位置的元素值（即 中位数）必须等于 $x$。如果区域内的城市数量是偶数，那么中间两个元素中，靠右（即数值较大）的那个元素的值必须等于 $x$。例如，集合 $\{1, 10, 2, 8, 4\}$ 的 中位数 是 $4$，而集合 $\{1, 2, 10, 8\}$ 的 中位数 是 $8$。

哥萨克将在这个国家再逗留恰好 $m$ 天。每天早晨他会告知他最喜欢的数字，而你需要告诉他 “优美区域” 的数量。

输入格式

第一行包含三个整数 $n$、$k$ 和 $g$ ($1 \leq n \leq 10^5$, $0 \leq k \leq n$, $0 \leq g \leq 11$) —— 分别表示国家中的城市数量、“人口交换” 操作的最大次数，以及测试点所属的区块编号。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$)，其中 $a_i$ 表示城市 $i$ 的人口数量。保证所有人口数量互不相同。

接下来的 $n - 1$ 行，每行包含两个整数 $v_i$ 和 $u_i$ ($1 \leq v_i, u_i \leq n$) —— 表示存在道路连接的两个城市编号。

下一行包含一个整数 $m$ ($1 \leq m \leq 10^5$) —— 哥萨克将在该有趣国家居住的天数。

再下一行包含 $m$ 个整数 $x_1, x_2,... ,x_m$ ($1 \leq x_i \leq 10^9$)，其中 $x_i$ 表示哥萨克在第 $i$ 天最喜欢的数字。

输出格式

输出 $m$ 个整数 —— 在 $m$ 天中，每天的 “优美区域” 数量。

5 1 0
1 3 4 2 5
1 2
1 3
3 4
3 5
5
1 2 3 4 5

3 4 5 4 3

提示

评分细则

• （5 分） $n,m \leq 10^3$, $k = 0$。
• （12 分） $n,m \leq 10^5$, $k = 0$。
• （5 分） $n,m \leq 10^3$, 城市 $i$ 与 $i + 1$ 之间有道路 ($1 \leq i \leq n-1$)。
• （9 分） $n,m \leq 10^5$, 城市 $i$ 与 $i + 1$ 之间有道路 ($1 \leq i \leq n-1$)。
• （5 分） $n,m \leq 10^3$, $k = n$。
• （11 分） $n,m \leq 10^5$, $k = n$。
• （8 分） $n,m \leq 10^2$。
• （9 分） $n,m \leq 10^3$。
• （11 分） $n \leq 10^5$, $m \leq 500$。
• （25 分） $n,m \leq 10^5$。

翻译由 DeepSeek V3 完成