P11195 [COTS 2021] 疫苗接种 Cijepise

译自 [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D2T1。$\texttt{5s,1G}$。

给定以 $1$ 为根的有 $N$ 个节点的有根树，记 $i$ 号点的点权为 $a_i$。 定义一次操作为： - 初始化 $u$ 为树根。 1. 设 $u$ 儿子中点权最大的点为 $v$（若有多个，则**等概率随机选取一个**）。令 $a_u\gets a_v$，$a_v\gets 0$。 2. 若 $v$ 为叶子，则删去 $v$，终止这个过程。否则令 $u\gets v$，回到 1。  定义 $f(v)$ 为：**在最坏情况下**，欲让 $a_v$ 尽可能快地（也就是使用尽量少的操作次数）出现在树根上，至少需要更改多少个点的点权（可以不更改）。 换句话说，我们定义在最坏情况下，$v$ 需要操作 $k$ 次到达树根。显然树的形态固定时，不同的点权会使得 $k$ 取不同的值，且 $k$ 存在一个下界。你需要修改若干个点的点权，使得 $k$ 取到下界，并最小化修改的数量。 点权可以被改为 $[0,2\times 10^9]$ 内的任意整数。 $Q$ 次询问给定 $v$，回答 $f(v)$。

第一行，一个正整数 $N$。 第二行，$N$ 个正整数 $a_i$。 接下来 $(N-1)$ 行，每行两个正整数 $u,v$，描述一条树边 $(u,v)$。 接下来一行，一个正整数 $Q$。 接下来 $Q$ 行，每行一个正整数 $v$，表示询问 $f(v)$。

输出 $Q$ 行，表示每个询问的答案。

对于 $100\%$ 的数据，保证 $1\le Q\le N\le 1\times 10^5$，$1\le a_i\le 10^9$，$1\le v\le N$，给出的是一棵树。 | 子任务编号 | $N\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 12 $ | 无 | $ 10 $ | | $ 2 $ | $ 300 $ | 无 | $ 11 $ | | $ 3 $ | $ 3\,000 $ | 有 | $ 12 $ | | $ 4 $ | $ 3\,000 $ | 无 | $ 13 $ | | $ 5 $ | $ 100\,000 $ | 有 | $ 20 $ | | $ 6 $ | $ 100\,000 $ | 无 | $ 34 $ | 特殊性质：$Q\le 1$。