#GYM104669K. Keys and the Subtree Permutation (Hard Version)
Keys and the Subtree Permutation (Hard Version)
Description
Keys needs your help! Tortles gave Keys a problem to solve, and the problem is as follows: You are given a tree rooted at node $1$ with N nodes $(1 \le N \le 2 \cdot 10^5)$. Each node has a value $P$ in the range of $[1, N]$. He was asked to solve the problem, for each node $i \in [1, N]$, find if the subtree of $i$ contains values that are a permutation of length size of that subtree. Unfortunately, Keys is too busy watching anime and playing Rinbot to solve the problem, so he turned to you for help. Please help Keys!
The first line contains a single integer $N$. The next line contains $N$ integers $P_1, P_2, ..., P_N$. The next $N - 1$ lines contain two integers $U$ and $V$, denoting an undirected edge between node $U$ and node $V$.
Print $N$ lines, with the $i$th line being "YES" if the subtree of $i$ contains values that are a permutation of length size of that subtree, and being "NO" otherwise.
Input
The first line contains a single integer $N$. The next line contains $N$ integers $P_1, P_2, ..., P_N$. The next $N - 1$ lines contain two integers $U$ and $V$, denoting an undirected edge between node $U$ and node $V$.
Output
Print $N$ lines, with the $i$th line being "YES" if the subtree of $i$ contains values that are a permutation of length size of that subtree, and being "NO" otherwise.
4
4 2 1 3
2 1
3 2
4 1
4
1 1 2 3
2 1
3 1
4 1
YES
YES
YES
NO
NO
YES
NO
NO
Note
For the first example:
The subtree at node $1$ is of size $4$ and contains the values $4, 2, 1, 3$, so it has a valid permutation.
The subtree at node $2$ is of size $2$ contains the values $2$ and $1$, so it has a valid permutation.
The subtree at node $3$ is of size $1$ and contains the value $1$, so it has a valid permutation.
The subtree at node $4$ is of size $1$ and contains the value $3$, so it does not have a valid permutation.