P10053 [CCO 2022] Bi-ing Lottery Treekets

In a parallel universe, everyone got a perfect score on CCO. Therefore, Troy needs to use a lottery to choose the winner. Each contestant will pick some numbers to create a ticket. A ticket is an array of size $N$, indexed from $1$ to $N$, where each element is a number from $0$ to $K$. The winning ticket is determined by dropping $K$ balls (numbered from $1$ to $K$) into a rooted binary tree in a random order. This tree has $N$ nodes (numbered from $1$ to $N$), and node $1$ is the root. Each ball has a designated drop node, where it will be dropped. When a ball is dropped into an empty node, or enters an empty node, one of the following three situations happens: 1. If all children of the current node are occupied by balls (or if a node has no children), then the current ball will stay at the current node. That is, it remains there and will not move anymore. 2. If the current node has exactly one empty child, then the current ball will move to that child. 3. If the current node has two empty children, and if the current ball was just dropped, it may move left or right. Otherwise, it will continue moving in the same direction as before. If not all $K$ balls can be dropped, then there is no determined winning ticket. This happens when a ball is dropped and its drop node is already occupied by another ball. If all $K$ balls are dropped successfully, then the final positions of the balls determine the winning ticket. The $i$-th element of the winning ticket is the label of the ball that stops at node $i$, or $0$ if no ball stops at node $i$. Troy wants to know the number of possible winning tickets. Since the answer can be very large, you only need to output it modulo $10^9+7$.

The first line contains two integers $N$ and $K$ separated by spaces, representing the number of nodes in the binary tree and the number of balls. The second line contains $K$ integers separated by spaces, where the $i$-th integer is the designated drop node of ball $i$. The last $N$ lines each contain two integers separated by spaces. The $i$-th of these lines contains $L_{i}$ and $R_{i}$, representing the left child and right child of node $i$, where $0$ means the child does not exist.

Output the number of winning tickets modulo $10^{9}+7$.

## Explanation for Sample 1  Consider the case where ball $1$ is dropped first. If ball $1$ moves left, then it will stop at node $2$. Afterwards, ball $2$ is dropped and may stop at node $4$ or $5$. If ball $1$ moves right, it will stop at node $5$. Then ball $2$ will stop at node $4$. Consider the case where ball $2$ is dropped first. Ball $2$ may move left or right and stop at node $4$ or $5$, respectively. Then, if ball $1$ moves left after being dropped, it will stop at node $2$. However, if ball $1$ moves right, it will stop at node $4$ or $5$, depending on which position ball $2$ did not occupy. The possible winning tickets are $[0,1,0,2,0]$, $[0,1,0,0,2]$, $[0,0,0,1,2]$, and $[0,0,0,2,1]$. ## Explanation for Sample 2  This sample satisfies the condition of the second subtask. Ball $3$ must be dropped first, because if ball $1$ or ball $2$ is dropped before ball $3$, it would stop at node $4$, which would prevent ball $3$ from being dropped. Therefore, we can drop ball $3$ first, then ball $2$, and finally ball $1$, or we can drop ball $3$ first, then ball $1$, and finally ball $2$. The corresponding winning tickets are $[0,1,2,3]$ and $[0,2,1,3]$. ## Constraints For all testdata, $1\leq N,K \leq 4000$. Subtask ID|Points|Range of $N$|Range of $K$|Additional constraints :-:|:-:|:-:|:-:|:-: $1$|$12$|$1 \leq N \leq 12$|$1 \leq K \leq 6$|None $2$|$16$|$1 \leq N \leq 4000$|$1 \leq K \leq 4000$|All nodes have no left child $3$|$36$|$1 \leq N \leq 4000$|$1 \leq K \leq 4000$|The $K$ drop nodes are all distinct $4$|$36$|$1 \leq N \leq 4000$|$1 \leq K \leq 4000$|None Translated by ChatGPT 5