编程题：关于深度优先搜索和逆序对的题应该不会很难吧这件事
### 背景知识
#### 深度优先搜索与 DFS 序
深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。以下伪代码描述了在树 $T$ 上进行深度优先搜索的过程：
procedure DFS(T, u, L) // T 是被深度优先搜索的树
// u 是当前搜索的节点
// L 是一个链表，保存了所有节点被第一次访问的顺序
append u to L // 将节点 u 添加到链表 L 的末尾
for v in u.children do // 枚举节点 u 的所有子节点 v
DFS(T, v) // 递归搜索节点 v
令 $r$ 为树 $T$ 的根，调用 DFS(T, r, L) 即可完成对 $T$ 的深度优先搜索，保存在链表 $L$ 中的排列被称为 DFS 序。相信聪明的你已经发现了，如果枚举子节点的顺序不同，最终得到的 DFS 序也会不同。
#### 逆序对
给定一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，该序列的逆序对数量是同时满足以下条件的有序数对 $(i, j)$ 的数量：
* $1 \le i < j \le n$；
* $a_i > a_j$。
### 问题求解
给定一棵 $n$ 个节点的树，其中节点 $r$ 为根。求该树所有可能的 DFS 序中逆序对数量之和。
### 输入格式
第一行输入两个整数 $n$，$r$（$2 \le n \le 3 \times 10^5$，$1 \le r \le n$）表示树的大小与根节点。
对于接下来的 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 与 $v_i$（$1 \le u_i, v_i \le n$），表示树上有一条边连接节点 $u_i$ 与 $v_i$。
### 输出格式
输出一行一个整数，表示该树所有可能的 DFS 序中逆序对数量之和。由于答案可能很大，请对 $10^9 + 7$ 取模后输出。
### 样例输入 1
in
5 3
1 5
2 5
3 5
4 3
### 样例输出 1
out
24
### 样例输入 2
in
10 5
10 2
2 5
10 7
7 1
7 9
4 2
3 10
10 8
3 6
### 样例输出 2
out
516
### 样例解释
下图展示了样例 1 中的树。
该树共有 $4$ 种可能的 DFS 序：
* $\{3, 4, 5, 1, 2\}$，有 6 个逆序对；
* $\{3, 4, 5, 2, 1\}$，有 7 个逆序对；
* $\{3, 5, 1, 2, 4\}$，有 5 个逆序对；
* $\{3, 5, 2, 1, 4\}$，有 6 个逆序对。
因此答案为 $6 + 7 + 5 + 6 = 24$。
答案：若无答案欢迎评论
考虑节点 $u$ 与 $v$ 满足 $u > v$，在多少 DFS 序中 $u$ 能排在 $v$ 前面。分以下几种情况：
* 若 $u$ 是 $v$ 的祖先，则所有 DFS 序中 $u$ 都在 $v$ 前面；
* 若 $v$ 是 $u$ 的祖先，则不存在这样的 DFS 序；
* 若 $u$ 与 $v$ 没有祖先关系，那么 $u$ 排在 $v$ 前面，意味着当搜索到 $u$ 和 $v$ 的 lca 时，先遍历了 $u$ 所在的子树，后遍历了 $v$ 所在的子树。遍历顺序可以看作是所有子节点的排列，很显然在一半的排列中，$u$ 在 $v$ 前面。
因此我们不妨先假设对于所有点对，都能在一半的 DFS 序中做出贡献。之后进行 DFS，遍历到节点 $u$ 时，如果它的祖先比 $u$ 大，那么我们少算了一半的 DFS 序；如果它的祖先比 $u$ 小，那么我们多算了一半的 DFS 序。因此本题的本质是计算每个节点的祖先有多少比它大（小），用树状数组维护即可。复杂度 $\mathcal{O}(n\log n)$。
另外只要一个节点枚举子节点的顺序不同，最终产生的 DFS 序就不同。因此 DFS 序的总数就是所有节点子节点数量阶乘相乘。
得分设计：
* 暴力枚举所有排列并检查，复杂度 $\mathcal{O}(n! \times n^2)$，15 分；
* 通过枚举计算每个节点的祖先有多少比它大（小），复杂度 $\mathcal{O}(n^2)$，23 分；
* 正确做法，30 分。
#### 深度优先搜索与 DFS 序
深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。以下伪代码描述了在树 $T$ 上进行深度优先搜索的过程：
procedure DFS(T, u, L) // T 是被深度优先搜索的树
// u 是当前搜索的节点
// L 是一个链表，保存了所有节点被第一次访问的顺序
append u to L // 将节点 u 添加到链表 L 的末尾
for v in u.children do // 枚举节点 u 的所有子节点 v
DFS(T, v) // 递归搜索节点 v
令 $r$ 为树 $T$ 的根，调用 DFS(T, r, L) 即可完成对 $T$ 的深度优先搜索，保存在链表 $L$ 中的排列被称为 DFS 序。相信聪明的你已经发现了，如果枚举子节点的顺序不同，最终得到的 DFS 序也会不同。
#### 逆序对
给定一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，该序列的逆序对数量是同时满足以下条件的有序数对 $(i, j)$ 的数量：
* $1 \le i < j \le n$；
* $a_i > a_j$。
### 问题求解
给定一棵 $n$ 个节点的树，其中节点 $r$ 为根。求该树所有可能的 DFS 序中逆序对数量之和。
### 输入格式
第一行输入两个整数 $n$，$r$（$2 \le n \le 3 \times 10^5$，$1 \le r \le n$）表示树的大小与根节点。
对于接下来的 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 与 $v_i$（$1 \le u_i, v_i \le n$），表示树上有一条边连接节点 $u_i$ 与 $v_i$。
### 输出格式
输出一行一个整数，表示该树所有可能的 DFS 序中逆序对数量之和。由于答案可能很大，请对 $10^9 + 7$ 取模后输出。
### 样例输入 1
in
5 3
1 5
2 5
3 5
4 3
### 样例输出 1
out
24
### 样例输入 2
in
10 5
10 2
2 5
10 7
7 1
7 9
4 2
3 10
10 8
3 6
### 样例输出 2
out
516
### 样例解释
下图展示了样例 1 中的树。
该树共有 $4$ 种可能的 DFS 序：
* $\{3, 4, 5, 1, 2\}$，有 6 个逆序对；
* $\{3, 4, 5, 2, 1\}$，有 7 个逆序对；
* $\{3, 5, 1, 2, 4\}$，有 5 个逆序对；
* $\{3, 5, 2, 1, 4\}$，有 6 个逆序对。
因此答案为 $6 + 7 + 5 + 6 = 24$。
答案：若无答案欢迎评论
考虑节点 $u$ 与 $v$ 满足 $u > v$，在多少 DFS 序中 $u$ 能排在 $v$ 前面。分以下几种情况：
* 若 $u$ 是 $v$ 的祖先，则所有 DFS 序中 $u$ 都在 $v$ 前面；
* 若 $v$ 是 $u$ 的祖先，则不存在这样的 DFS 序；
* 若 $u$ 与 $v$ 没有祖先关系，那么 $u$ 排在 $v$ 前面，意味着当搜索到 $u$ 和 $v$ 的 lca 时，先遍历了 $u$ 所在的子树，后遍历了 $v$ 所在的子树。遍历顺序可以看作是所有子节点的排列，很显然在一半的排列中，$u$ 在 $v$ 前面。
因此我们不妨先假设对于所有点对，都能在一半的 DFS 序中做出贡献。之后进行 DFS，遍历到节点 $u$ 时，如果它的祖先比 $u$ 大，那么我们少算了一半的 DFS 序；如果它的祖先比 $u$ 小，那么我们多算了一半的 DFS 序。因此本题的本质是计算每个节点的祖先有多少比它大（小），用树状数组维护即可。复杂度 $\mathcal{O}(n\log n)$。
另外只要一个节点枚举子节点的顺序不同，最终产生的 DFS 序就不同。因此 DFS 序的总数就是所有节点子节点数量阶乘相乘。
得分设计：
* 暴力枚举所有排列并检查，复杂度 $\mathcal{O}(n! \times n^2)$，15 分；
* 通过枚举计算每个节点的祖先有多少比它大（小），复杂度 $\mathcal{O}(n^2)$，23 分；
* 正确做法，30 分。
