CCCC L3-032 关于深度优先搜索和逆序对的题应该不会很难吧这件事 【树状数组】

https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582895035215872

题意

给你一棵树，给定树根，要求树的所有结点编号的dfs序中逆序对的数量总和，对结果模 \(10^9 + 7\)

树的结点数 \(\leq 3*10^5\)

思路

首先会想到，树的dfs序的方案数是 \(\prod_{i=1}^{n}cntson[i]\)

接下来分析什么情况下树的dfs序会产生逆序对。

把会产生逆序对的情况分为两种，第一种是两个点是祖先和子孙的关系，那么如果祖先更大，这一对点一定会产生逆序对，对答案的贡献是dfs序的方案数

第二种是两个点不是祖先和子孙的关系，又因为每个点的编号互不相同，所以它们有1/2的概率会产生逆序对，对答案的贡献是dfs序的方案数/2

那么最后的答案就是 第一种情况的数量 * 第一种情况的点对贡献 + 第二种情况的数量 * 第二种情况的点对贡献

统计第一种情况的数量：需要知道一个点的祖先中有多少比它大，可以在dfs结点时模拟一个栈，当遍历到某个点就把它入栈，遍历子结点时它就在栈中，遍历完子节点后把它出栈，然后用树状数组统计数量

第二类点，只用分析一个父亲结点的子树的情况，然后会发现它就包含了所有第二类情况

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10, mod = 1e9 + 7;
int n, r;
int a[N];
vector<int> e[N];
ll fac[N], base, c[N], s, s2;
int sz[N];

// 第二类点：不是祖先也不是子孙的点

ll qpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b%2){
			ans*=a;
			ans%=mod; 
		}
		a*=a;
		a%=mod;  
		b/=2;
	}
	return ans;  
}

inline int lowbit(int x) {return x & -x;}

void upd(int x, ll k){
	while(x<=n){
		c[x]+=k; 
		x+=lowbit(x);
	}
}

ll sum(int x){
	ll res=0;
	while(x){
		res+=c[x]; 
		x-=lowbit(x);
	}
	return res;
}

void init(int n) {
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
}

void dfs(int u, int fa) {
    sz[u] = 1;
    s = (s + sum(n) - sum(u)) % mod;
    upd(u, 1);
    ll t = 0;//
    int cn = 0;
    for(auto v : e[u]) {
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        cn++;
        s2 += t * sz[v]; s2 %= mod;
		t += sz[v];
    }
    base = base * fac[cn] % mod;
    upd(u, -1);
}

int main() {
    scanf("%d%d", &n, &r);
    init(n);
    for(int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    base = 1;
    dfs(r, 0);
    ll ans = s * base % mod;
    // ans = (ans + (1ll * n * (n - 1) / 2 - s - s2) * base % mod * qpow(2, mod - 2) % mod) % mod;
    ans = (ans + s2 * base % mod * qpow(2, mod - 2) % mod) % mod;
    printf("%lld\n", ans);
    // cout << "base: " << base << endl;
    system("pause");
    return 0;
}