L3-032 关于深度优先搜索和逆序对的题应该不会很难吧这件事(天梯赛)

分析：

不可能把所有情况都给列出来 但是好像这样可以得一半的分数

考虑每个点对 对答案产生的贡献

发现具有父子关系的点对无论什么情况 相对位置都是固定的 产生的贡献就是再乘上f[rt] （f[rt]表示整个树的不同dfs序的种类）

关键在于不具有父子关系的点对 该如何考虑

假如<a,b>是不具有父子关系的两点 LCA(a,b)=u

u通向含有a子树的亲儿子为X u通向含有b子树的亲儿子为Y

考虑u子树的遍历情况 X在Y前 Y在X前 两种情况各占一半

所以贡献就是再乘f[rt]/2

#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;
}