#P7997. [2021年山东省队集训]心理阴影

    ID: 8010 传统题 1500ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-期望 DP树形 DP期望线性性全概率公式DFS 序子树转区间逆元线性递推

[2021年山东省队集训]心理阴影

题目描述

“结束了。”小猫眼睁睁地看着右上角的时间倒数到 00:00:00。成绩表上只留下灰色的 −111。

这场 CodeForces 成为了小猫的心理阴影,所以他今天要滥用出题人的权力,将这一不美好的回忆强加于你。

现在你被迫解决根据小猫看错的题意出的题:有一棵 nn 个点的有根树,点的标号为 1,2,...,n1, 2, . . . , n, rr 为树的根。现在有一个排列,满足若 uu 是 vv 的父结点,则 uu 排在 vv 之前。求所有如此的排列的逆序数平均值。

对 109+710^9 + 7 取模,具体地,若答案为分数 p/qp/q, 则输出 x∈[0,109+7)x\in [0, 10^9 + 7) 使得 qx≡p(mod109+7)qx\equiv p\pmod {10^9 + 7}。

输入格式

第一行两个正整数 n,rn, r, 分别表示点数和根的编号。保证 1≤r≤n1 ≤ r ≤ n。

接下来 n−1n − 1 行每行两个正整数 u,vu, v, 表示一条边的两端的编号。保证输入的所有边构成一棵树。

输出格式

一行一个正整数表示逆序数平均值,对 109+710^9 + 7 取模的结果。

样例 #1

样例输入 #1

5 3
1 2
1 3
2 4
3 5

样例输出 #1

500000007

提示

样例解释

3 5 1 2 4:55 对逆序

3 1 5 2 4:44 对逆序

3 1 2 5 4:33 对逆序

3 1 2 4 5:22 对逆序

平均: 7/2≡500000007(mod109+7)7/2\equiv 500000007 \pmod {10^9 + 7}

数据范围

对于 20%20\% 数据,n≤9n ≤ 9;

对于 50%50\% 数据,n≤50n ≤ 50;

对于 100%100\% 数据,n≤4096n ≤ 4096。