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;

}

巴特西

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

题意

思路

code

最新文章

热门文章

巴特西

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

题意

思路

code

最新文章

热门文章

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