Send Tree to Charlie
Contest: Codeforces Round 601 (Div. 1)
Difficulty rating: 3300
Tags: combinatorics, dfs and similar, dsu, trees

Christmas was knocking on the door, and our protagonist, Bob, was preparing a spectacular present for his long-time second best friend Charlie. As chocolate boxes are lame, he decided to decorate a tree instead. Bob's tree can be represented as an undirected connected graph with $$$n$$$ nodes (numbered $$$1$$$ to $$$n$$$) and $$$n-1$$$ edges. Initially, Bob placed a decoration with label $$$i$$$ on node $$$i$$$, for each $$$1 \le i \le n$$$. However, as such a simple arrangement is lame, he decided to shuffle the decorations a bit. Formally, Bob did the following steps:

- First, he listed the $$$n-1$$$ edges in some order.
- Then, he considered the edges one by one in that order. For each edge $$$(u, v)$$$, he swapped the decorations of node $$$u$$$ with the one of node $$$v$$$.

After finishing, Bob seemed satisfied with the arrangement, so he went to sleep.

The next morning, Bob wakes up only to find out that his beautiful arrangement has been ruined! Last night, Bob's younger brother Bobo dropped some of the decorations on the floor while he was playing with the tree. Fortunately, no decorations were lost, so Bob can repair the tree in no time. However, he completely forgets how the tree looked like yesterday. Therefore, given the labels of the decorations still on the tree, Bob wants to know the number of possible configurations of the tree. As the result can be quite large, Bob will be happy if you can output the result modulo $$$1000000007$$$ ($$$10^9+7$$$). Note that, it is possible that there exists no possible configurations.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 500\,000$$$) — the number of nodes.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), denoting that there is an edge connecting two nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$). For each $$$i$$$, $$$a_i = 0$$$ means that the decoration of node $$$i$$$ has been dropped on the floor. Otherwise, $$$a_i$$$ is the label of the decoration of node $$$i$$$. It is guaranteed that no label appears more than once.

Output format:
Output the number of possible configurations modulo $$$1000000007$$$ ($$$10^9+7$$$).

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, the possible configurations of the tree are $$$[2, 4, 1, 3]$$$ and $$$[3, 4, 2, 1]$$$.

In the second example, note that while there are $$$4! = 24$$$ possible permutations of the edges, each of them results in a possible configuration, there are only $$$12$$$ different configurations.

In the third example, it is easy to see that the decoration $$$1$$$ cannot stay at node $$$1$$$ after the swaps.

Example input:
4
3 4
2 4
4 1
0 4 0 0

Example output:
2

Example input:
5
1 2
2 4
3 4
5 4
0 0 0 0 0

Example output:
12

Editorial:
Let's solve an easier version of this problem first: when all $$$a_i$$$ is equal to $$$0$$$. Let $$$P[1..n-1]$$$ be some order of edges. If $$$n=2$$$ then the answer is clearly $$$1$$$. Otherwise, consider any leaf $$$u$$$ and its neighbor $$$v$$$. The label of $$$u$$$ in the end will depend solely on the relative position of the edge $$$(u, v)$$$ compared to other edges incident to $$$v$$$ in $$$P$$$. We can also prove that if that relative position is fixed then the final configuration will be the same. Therefore, if we add $$$u$$$ to the tree, the answer will be multiplied by $$$deg(v)$$$. It follows that the answer in this case will be $$$\displaystyle\prod_{u=1}^{n} deg(u)!$$$. We can also see that each configuration can be obtained by ordering the edges incident to $$$u$$$ for each vertex $$$u$$$.
Now, let's consider some constraint of the form $$$a[u] = v$$$. If $$$u = v$$$ then clearly there's no such configuration. Otherwise, it will create some conditions of the orderings in each vertex. Formally, let $$$B(u)$$$ be the ordering of edges incident to $$$u$$$, and $$$u, t_1, \ldots, t_k, v$$$ be the path from $$$u$$$ to $$$v$$$, we have the following conditions:
• $$$(u, t_1)$$$ is the first edge in $$$B(u)$$$.
• $$$(t_i, t_{i-1})$$$ must be followed immediately by $$$(t_i, t_{i+1})$$$ in $$$B(t_i)$$$, for all $$$1 \le i \le k$$$.
• $$$(v, t_k)$$$ is the last edge in $$$B(v)$$$.
Another thing to note is that in the final configuration, the sum of distance between $$$u$$$ and the vertex that contains label $$$u$$$ will be exactly $$$2n-2$$$ because each swap increases the sum by exactly $$$2$$$. Therefore, we can quit immediately upon finding out that the sum is larger than $$$2n-2$$$, and by that we ensure the total number of conditions will be $$$O(n)$$$.
Now, we can solve each vertex independently. For each vertex, there will be no possible configurations iff at least one of the following holds:
• Some edge follows or is followed by more than one edge.
• The conditions create some cycles.
• The conditions create a path from the first edge to the last edge, but there exists some edge not in it.
Otherwise, the conditions create some chains. We then multiply the answer by $$$k!$$$, where $$$k$$$ is the number of such chains, excluding those that contain the first edge or the last edge.
Time complexity: $$$O(n)$$$.