problem
背景知识
深度优先搜索与 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
,⋯,a
n
，该序列的逆序对数量是同时满足以下条件的有序数对 (i,j) 的数量：
1≤i<j≤n；
a
i
a
j
。
问题求解
给定一棵 n 个节点的树，其中节点 r 为根。求该树所有可能的 DFS 序中逆序对数量之和。
输入格式
第一行输入两个整数 n，r（2≤n≤3×10
5
，1≤r≤n）表示树的大小与根节点。
对于接下来的 (n−1) 行，第 i 行输入两个整数 u
i
与 v
i
（1≤u
i
,v
i
≤n），表示树上有一条边连接节点 u
i
与 v
i
。
输出格式
输出一行一个整数，表示该树所有可能的 DFS 序中逆序对数量之和。由于答案可能很大，请对 10
9
+7 取模后输出。
样例输入 1
5 3
1 5
2 5
3 5
4 3
样例输出 1
24
样例输入 2
10 5
10 2
2 5
10 7
7 1
7 9
4 2
3 10
10 8
3 6
样例输出 2
516
样例解释
下图展示了样例 1 中的树。
solution
- 单独考虑一个dfs序，存在父子关系的点对是否逆序数已确定（一定是父亲在前面，儿子在后面），这样的节点对答案的贡献就直接为这个树的DFS序的种类数。
不存在父子关系的点对是否逆序数的概率各一半（要么A先，要么B先），这样的结点对于答案的贡献其实就是这个树的DFS序的种类数除以2。
- 如何求树的DFS序种类数？ 递推做法，考虑维护一个子树u的dfs序数f[u]，根据乘法原理，当前节点的dfs序数 = ∏以其子节点为根的子树的dfs序数×子节点的排列数，叶子节点的DFS序种类数为1。
- 如何求解两种点对的数目？ 对于存在父子关系的，求出对于遍历到当前节点，经过的所有点的点数（树状数组的所有值）即可。对于不存在的，可以拿总点数n*(n-1)/2减去。
- 如何计算已确定的逆序对数量？ 在dfs的过程中在值域上建立树状数组，对于当前节点，求出祖先中比当前数大的数的个数，累加就是逆序对。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 3e5+10;
const LL mod = 1e9+7;
LL n, rt;
vector<LL>G[maxn];
//排列组合
LL fac[maxn];
void init(){
fac[0]=1; for(LL i = 1; i < maxn; i++)fac[i]=fac[i-1]*i%mod;
}
LL mpow(LL a, LL x) {
if(x==0)return 1;
LL t = mpow(a, x>>1);
if(x%2==0)return t*t%mod;
return t*t%mod*a%mod;
}
//树状数组求逆序对
LL b[maxn];
void add(LL x, LL v){ for(LL i = x; i <= n; i+=i&(-i))(b[i]+=v)%=mod;}
LL query(LL x){ LL ans=0;for(LL i=x;i>0;i-=i&(-i))(ans+=b[i])%=mod;return ans%mod;}
//题目
LL f[maxn];//为以u为子树的dfs序方案数
LL cnt1 = 0, cnt2 = 0;//在一个dfs序中确定, 不确定的逆序对数量
void dfs(LL x, LL fa){
f[x] = 1;
for(LL to : G[x]){
if(to==fa)continue;
cnt1 = (cnt1+query(n)-query(to)+mod)%mod;//祖先里比当前大的数的个数
cnt2 = (cnt2+query(to))%mod; //祖先里比当前小的数的个数
add(to, 1);
dfs(to, x);
add(to, -1);
f[x] = f[x]*f[to]%mod;
}
//当前节点的dfs序数 = ∏以其子节点为根的子树的dfs序数×子节点的排列数
LL num = (x==rt ? G[x].size() : G[x].size()-1);
f[x] = f[x]*fac[num]%mod;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
init();
cin>>n>>rt;
for(LL i = 1; i <= n-1; i++){
LL u, v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
add(rt, 1);
dfs(rt, -1);
LL num = ((n*(n-1)%mod*mpow(2,mod-2)%mod -cnt1-cnt2)%mod+mod)%mod;//没有父子关系的点对数量
LL ans = f[rt]*(cnt1+num*mpow(2,mod-2)%mod)%mod;//cnt1就是有父子关系的逆序对数
// cout<<cnt1<<" "<<cnt2<<"\n";
cout << ans << "\n";
return 0;
}
