P8575 "DTOI-2" River of Stars

> The stars are sparse as the river’s shadow turns, the frost is heavy and the moonlight stands alone.

The ruler of the stars has a star chart, which can be abstracted as a tree rooted at node $1$. Each node $i$ on the tree has a red star and a blue star, with brightness denoted by $\text{Red}_i$ and $\text{Blue}_i$. Now, the ruler of the stars wants to know, for each node $x$, how many nodes in its subtree (excluding the node itself) satisfy: their red star brightness is less than or equal to the red star brightness of $x$, and their blue star brightness is less than or equal to the blue star brightness of $x$. You need to output the answer for each node in increasing order of node index. To reduce the amount of output, **if the answer is $0$, you do not need to output it.**

The first line contains an integer $n$. The next $n - 1$ lines each contain two positive integers $u, v$, indicating that the tree has an edge $(u, v)$. The next $n$ lines each contain two integers, representing $\text{Red}_i$ and $\text{Blue}_i$.

For each node whose answer is non-zero, output one line containing an integer, which is the answer for that node.

### Sample Explanation For node $1$, the children that are less than or equal to it are $6, 7, 8, 9, 10$, so output $5$. For node $4$, the child that is less than or equal to it is $6$, so output $1$. For nodes $5$ to $10$, there are no children that are less than or equal to them, so do not output anything. ### Constraints | $\textbf{Subtask}$ | $n\le$ | Special Property | Total Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $1000$ | None | $10$ | | $2$ | $5\times 10^4$ | None | $20$ | | $3$ | $10^5$ | $-200\le \text{Red}_i, \text{Blue}_i \le 200$ | $20$ | | $4$ | $2\times 10^5$ | The tree is a chain | $20$ | | $5$ | $2\times 10^5$ | None | $30$ | For all testdata, it is guaranteed that $n \le 2\times 10^5$ and $-10^9 \le \text{Red}_i, \text{Blue}_i \le 10^9$. Translated by ChatGPT 5