CF1254E Send Tree to Charlie

圣诞节即将来临，主角 Bob 正在为他多年的第二好朋友 Charlie 准备一份精彩的礼物。由于巧克力盒太普通，他决定装饰一棵树。Bob 的树可以表示为一个有 $n$ 个节点（编号为 $1$ 到 $n$）和 $n-1$ 条边的无向连通图。最初，Bob 在每个节点 $i$ 上放置了标签为 $i$ 的装饰品，对于每个 $1 \leq i \leq n$。然而，这样的简单排列太无趣了，他决定稍微打乱一下装饰品。具体来说，Bob 按如下步骤操作： - 首先，他以某种顺序列出了 $n-1$ 条边。 - 然后，他按顺序依次考虑每条边。对于每条边 $(u, v)$，他交换了节点 $u$ 和节点 $v$ 上的装饰品。 完成后，Bob 对这个排列很满意，于是去睡觉了。 第二天早上，Bob 醒来却发现他精心布置的装饰品被毁了！昨晚，Bob 的弟弟 Bobo 在玩树的时候把一些装饰品掉到了地上。幸运的是，没有装饰品丢失，所以 Bob 很快就能修复树。然而，他完全忘记了昨天树上的装饰品是如何排列的。因此，给定现在树上还挂着的装饰品标签，Bob 想知道可能的树的排列方案数。由于结果可能很大，请输出结果对 $1000000007$（$10^9+7$）取模。注意，可能不存在任何可行的排列方案。

第一行包含一个整数 $n$（$2 \leq n \leq 500\,000$），表示节点数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示有一条连接节点 $u$ 和 $v$ 的边。保证给定的边构成一棵树。 最后一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq n$）。对于每个 $i$，$a_i = 0$ 表示节点 $i$ 上的装饰品掉到了地上。否则，$a_i$ 表示节点 $i$ 上装饰品的标签。保证没有标签出现超过一次。

输出可能的排列方案数，对 $1000000007$（$10^9+7$）取模。

在第一个样例中，树的可能排列为 $[2, 4, 1, 3]$ 和 $[3, 4, 2, 1]$。 在第二个样例中，虽然边的排列有 $4! = 24$ 种可能，但每种都会得到一个可能的排列，实际上只有 $12$ 种不同的排列。 在第三个样例中，很容易看出装饰品 $1$ 不可能通过交换后仍然留在节点 $1$ 上。 由 ChatGPT 4.1 翻译