Background

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

Problem Description

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.

Input Format

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$.

Output Format

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

10
2 1
3 1
4 3
5 1
6 4
7 2
8 2
9 4
10 3
3 1
2 4
-3 3
4 -2
-2 3
-3 -6
-5 -1
-4 -7
-5 -1
-7 -7

5
2
3
1

Hint

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

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