题目背景

译自 Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) 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$ 尽可能快地（也就是使用尽量少的操作次数）出现在树根上，至少需要更改多少个点的点权（可以不更改）。点权可以被改为 $[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$ 行，表示每个询问的答案。

3
1 2 3
1 2
1 3
3
1
2
3

0
1
0

7
45 13 19 3 81 27 77
1 2
1 3
1 4
3 5
3 6
4 7
3
5
6
7

0
1
1

8
23 4 9 7 11 4 1 18
2 1
3 2
4 2
5 2
6 3
7 4
8 1
3
2
3
7

1
2
3

提示

对于 $100\%$ 的数据，保证 $1\le Q\le N\le 2\times 10^5$，$1\le a_i\le 10^9$，$1\le v\le N$，给出的是一棵树。

特殊性质：$Q\le 1$。