P11195 [COTS 2021] Vaccination Cijepise

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

You are given a rooted tree with $N$ nodes, rooted at $1$. Let the value (weight) of node $i$ be $a_i$. Define one operation as follows: - Initialize $u$ as the root of the tree. 1. Let $v$ be the child of $u$ with the largest value (if there are multiple, choose one **uniformly at random**). Set $a_u\gets a_v$ and $a_v\gets 0$. 2. If $v$ is a leaf, delete $v$ and terminate this process. Otherwise set $u\gets v$ and go back to step 1.  Define $f(v)$ as: **in the worst case**, in order to make $a_v$ appear at the root as fast as possible (i.e., using as few operations as possible), what is the minimum number of nodes whose values must be changed (you may also choose not to change any). In other words, in the worst case, node $v$ needs $k$ operations to reach the root. Obviously, when the tree shape is fixed, different node values will make $k$ take different values, and $k$ has a lower bound. You need to modify the values of some nodes so that $k$ reaches this lower bound, while minimizing the number of modifications. A node value can be changed to any integer in $[0,2\times 10^9]$. There are $Q$ queries. Given $v$, output $f(v)$.

The first line contains one positive integer $N$. The second line contains $N$ positive integers $a_i$. The next $(N-1)$ lines each contain two positive integers $u,v$, describing an edge $(u,v)$ in the tree. The next line contains one positive integer $Q$. The next $Q$ lines each contain one positive integer $v$, representing a query for $f(v)$.

Output $Q$ lines, each being the answer to one query.

For $100\%$ of the testdata, it is guaranteed that $1\le Q\le N\le 1\times 10^5$, $1\le a_i\le 10^9$, $1\le v\le N$. The input is a tree. ## Constraints | Subtask ID | $N\le$ | Special Property | Score | | :--: | :--: | :--: | :--: | | $1$ | $12$ | None | $10$ | | $2$ | $300$ | None | $11$ | | $3$ | $3\,000$ | Yes | $12$ | | $4$ | $3\,000$ | None | $13$ | | $5$ | $100\,000$ | Yes | $20$ | | $6$ | $100\,000$ | None | $34$ | Special Property: $Q\le 1$。 Translated by ChatGPT 5