← 返回题目列表

Codeforces · 1254/E

E. 将树发送给查理

中文机器翻译题面 查看原题

圣诞节即将来临,我们的主角鲍勃正在为他的第二好朋友查理准备一份精美的礼物。由于巧克力盒很蹩脚,他决定装饰一棵树。 Bob 的树可以表示为具有 $$$n$$$ 节点(编号为 $$$1$$$ 到 $$$n$$$)和 $$$n-1$$$ 边的无向连通图。最初,Bob 在节点 $$$i$$$ 上放置了一个带有标签 $$$i$$$ 的装饰,每个 $$$1 \le i \le n$$$。不过,这样简单的布置有些蹩脚,所以他决定稍微调整一下装饰。鲍勃正式执行了以下步骤:

- 首先,他按某种顺序列出了 $$$n-1$$$ 边。
- 然后,他按照顺序一一考虑边缘。对于每条边 $$$(u, v)$$$,他将节点 $$$u$$$ 的装饰与节点 $$$v$$$ 的装饰交换。

完成后,鲍勃似乎对这个安排很满意,所以他就去睡觉了。

第二天早上,鲍勃醒来却发现他美好的安排被毁了!昨晚,鲍勃的弟弟波波在玩圣诞树时,把一些装饰品掉在了地板上。幸运的是,装饰品没有丢失,所以鲍勃可以立即修复这棵树。然而,他完全忘记了昨天那棵树是什么样子。因此,鉴于仍在树上的装饰标签,鲍勃想知道树的可能配置数量。由于结果可能非常大,如果您可以输出对 $$$1000000007$$$ ($$$10^9+7$$$) 取模的结果,Bob 会很高兴。请注意,可能不存在任何可能的配置。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500\,000$$$) — 节点数。

接下来的 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$),表示有一条边连接两个节点 $$$u$$$ 和 $$$v$$$。保证给定的边形成一棵树。

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 the number of possible configurations modulo $$$1000000007$$$ ($$$10^9+7$$$).

示例

输入 #1

4
3 4
2 4
4 1
0 4 0 0

输出 #1

2

输入 #2

5
1 2
2 4
3 4
5 4
0 0 0 0 0

输出 #2

12

输入 #3

3
1 2
1 3
1 0 0

输出 #3

0

注意

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.