L3-032 关于深度优先搜索和逆序对的题应该不会很难吧这件事 有趣的数据结构题

传送门:PTA

题目描述:

给定一棵 n 个节点的树，其中节点 r 为根。求该树所有可能的 DFS 序中逆序对数量之和。
输入:
10 5
10 2
2 5
10 7
7 1
7 9
4 2
3 10
10 8
3 6
输出:
516

唉,由于近期事情比较多以及某些个人因素导致好久没有更新博客了,今天碰到了一道有意思的数据结构题,故决定更新一篇博客

首先看完题目会发现题意十分简单,就是求所有$dfs$序的逆序对数总和

显然对于一个点$u$来说,因为枚举$u$的儿子$vi$的顺序不同会导致不同的逆序对.把玩一下$dfs$的遍历方式,我们会发现一些有意思的规律

对于树上的两个点$u,v$来说,假设$u,v$是祖先和儿子关系(不妨假设$u$是祖先),那么根据我们的$dfs$的遍历顺序,我们会发现无论怎么遍历$u$在$dfs$序的位置肯定是在$v$的前面的.那么对于所有的点对$u,v$来说,都可以对答案进行一个贡献.那么此时的贡献总数显然就是一棵树中这样的$u,v$的个数$\ast$$dfs$序的个数.对于$dfs$序的个数的求法,等会再详细介绍.

再来讲一下如何求出这样的点对的个数.我们可以使用树状数组进行维护.具体操作方法可以见这道题.在那道题中我有详细解释,此处就不在赘述了.

对于树上的所有点对<u,v>来说,显然除了祖先儿子的关系还有一种就是不是祖先儿子的关系.对于这样的点对<u,v>来说,因为$u$和$v$肯定是不同的,又因为不是祖先儿子的关系,所以在$dfs$序中肯定存在这样的情况:$u$在$v$的前面或者$v$在$u$的前面,那么对于上述两种情况来说,此时两种情况肯定是有且只有一种情况是可以提供贡献的.也就是对于所有的$dfs$序来说,有一半$dfs$序的点对<u,v>是可以进行贡献的.那么此时我们的总贡献就是所有的$dfs$序的个数的一半乘上所有的这样的点对<u,v>的个数

现在再来讲一下这样的<u,v>的个数应该怎么求.

int kkk=0;
for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==per_u) continue;dfs(v,u);Size[u]+=Size[v];sum2=(sum2+Size[v]*kkk%mod)%mod;kkk=(kkk+Size[v])%mod;}

假设我们有这样一棵树,枚举到了u,此时我们统计一下u这棵子树的所有答案.
我们会发现有两种情况:
1.一种情况就是$v1,v2,v3$的自身子树的点对个数,这种情况我们可以使用类似于分治的思想在dfs中顺便解决,因为求出自身的点对个数的方法就是求出u这棵子树的方法
2.$v1,v2,v3$跨子树构成的点对.我们可以这样进行统计,当枚举到$vi$时,我们记$vi$的贡献就是 S i z e [ v i ] ∗ ∑ k = 1 i − 1 S i z e [ k ] Size[vi]*\\sum_{k=1}^{i-1}Size[k] Size[vi]∗∑k=1i−1​Size[k].这样我们可以不重不漏的计算出所有的点对个数

现在再来讲一下如何求出$dfs$序的个数.对于当前的u节点来说,存在儿子$vi$,那么此时的$dfs$序来说,我们会发现显然所有的父亲和儿子节点在$dfs$序中显然是连在一起的(可能有点抽象,仔细理解一下).那么我们此时有两种改变$dfs$的方法,一种就是调整$vi$的儿子节点的遍历顺序,另一种就是调整$vi$的遍历顺序.总贡献显然就是两者相乘.我们会发现调整$vi$的遍历顺序的方法数是$Size[u]!$.我们此时又可以使用分治的思想不断递归的去解决这道题.我们会发现最终的总贡献就是所有的$Size[u]$相乘,也就是所有的节点的子节点个数相乘.简单来说就是只要一个节点枚举子节点的顺序不同，最终产生的 DFS 序就不同。因此 DFS 序的总数就是所有节点子节点数量阶乘相乘。

因为取模的原因,对于除2我们需要使用逆元进行解决

下面是具体的代码部分;

#include <bits/stdc++.h>
using namespace std;
#define maxn 300010
#define int long long
const int mod=1e9+7;
int n,r;
inline int lowbit(int x) {return x&(~x+1);
}
int tree[maxn];
void Add(int pos,int val) {while(pos<=n) {tree[pos]+=val;pos+=lowbit(pos);}
}
int query(int pos) {int ans=0;while(pos) {ans+=tree[pos];pos-=lowbit(pos);}return ans;
}
int fac[maxn];
void init() {fac[0]=1;for(int i=1;i<=n;i++) {fac[i]=fac[i-1]*i%mod;}
}
int qpow(int a,int b) {int ans=1;while(b) {if(b&1) ans=(ans*a)%mod;b>>=1;a=(a*a)%mod; }return ans;
} 
vector<int>edge[maxn];
int sum1=0;int sum2=0;int Size[maxn];int Z=1;
void dfs(int u,int per_u) {Size[u]=1;sum1=(sum1+query(n)-query(u))%mod;Add(u,1);int kkk=0;int kk=0;for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==per_u) continue;dfs(v,u);kk++;Size[u]+=Size[v];sum2=(sum2+Size[v]*kkk%mod)%mod;kkk=(kkk+Size[v])%mod;}Add(u,-1);Z=(Z*fac[kk])%mod;
}
signed main() {cin.sync_with_stdio(false);cin>>n>>r;init();for(int i=1;i<=n-1;i++) {int u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}dfs(r,0);sum1=(sum1*Z)%mod;sum2=(sum2*Z)%mod*qpow(2,mod-2)%mod;cout<<(sum1+sum2)%mod<<endl;return 0;
}