树与图上计数问题：Prufer序列与LGV引理

树与图上的计数问题

Prufer序列

起源于对\(Cayley\)定理的证明，但是其功能远不止于此

• \(Tree->Prufer:\)

  ①从树上选择编号最小的叶子节点，序列的下一位为其父节点的编号。

  ②删去该叶子节点。

  ③重复①和②，直到树只剩下两个节点，此时序列的长度刚好为 n−2 。

• \(Prufer—>Tree:\)

  ①选择编号最小的叶子节点（即未出现在序列中的节点），其父节点就是序列的第 i （ i 初始为1）个元素。

  ②由性质可得，其父节点的度数为其出现次数+1。将该叶子节点删去，其父节点度数-1。若度数变成1，则父节点也成为叶子节点。

  ③将 i 加一，然后重复①和②，直到序列的每一个元素都使用完毕。

ll p[N];
ll d[N];//度数
ll f[N];//连边
ll ans=0;
void Prufer_To_Tree(ll n)
{
    //f记录1-n-1的连边情况
    for(int i=1;i<=n-2;++i) cin>>p[i],d[p[i]]++;
    p[n-1]=n;
    for(int i=1,j=1;i<n;++i,++j)
    {
        while(d[j]) j++;
        f[j]=p[i];//把最小的叶往prufer序列第一个点上接 对应减掉度数

        while(i<n&&!--d[p[i]]&&p[i]<j) f[p[i]]=p[i+1],i++;
        //如果序列第一个点减掉度数后产生了新的更小的叶 就往序列下一个点上接
    }
    for(int i=1;i<=n;++i) ans^=1ll*i*f[i];
}
void Tree_To_Prufer(ll n)
{
    for(int i=1;i<n;++i) cin>>f[i],d[f[i]]++;
    for(int i=1,j=1;i<=n-2;++i,++j)
    {
        while(d[j]) j++;
        p[i]=f[j];
        while(i<=n-2&&!--d[p[i]]&&p[i]<j) p[i+1]=f[p[i]],i++;
    }
    for(int i=1;i<=n-2;++i) ans^=1ll*i*p[i];
}

由此我们发现两者是一一对应的，也就是双射，所以大小为n的有标号无根树的个数等于长度为\(n-2\)的prufer序列的个数，自然为\(n^{n-2}\)，\(Cayley\)定理得证

Prufer序列的性质

由Prufer序列构造的过程，我们可以发现其具有两个显而易见的性质。

• 构造完后剩下的两个节点里，一定有一个是编号最大的节点。

• 对于一个 n 度的节点，其必定在序列中出现 n−1 次。因为每次删去其子节点它都会出现一次，最后一次则是删除其本身。一次都未出现的是原树的叶子节点。

应用

1、无向完全图的不同生成树数：

\(n^{n−2}\) 。

2、 n 个点的无根树计数：

同上问题。

3、 n 个点的有根树计数：

对每棵无根树来说，每个点都可能是根，故总数为 \(n^{n−2}×n=n^{n−1}\) 。

4、 n 个点，每点度分别为 \(d_i\) 的无根树计数：

显然就是一个多重集，答案为\(\frac{(n-2)!}{\prod_{i=1}^{n}d_i-1}\)

5、 有标号的完全二分图\(K_{n,m}\)的生成树个数为\(n^{m-1}m^{n-1}\):

考虑将其生成树的prufer序列按照原本顺序分成\(f_i\leq n,f_i>n\)两部分。

对于\(f_i\leq n\)的部分，一定是删去某个标号\(>n\)的点之后留下\(f_i\)的，因为这是一张二分图。所以该部分的点一定恰好有\(m-1\)个（右部有m个点，整张图删完之后一定在左右部各留下一个点，所以右部一共要删去\(m-1\)个点）

\(f_i>n\)部分同理。

所以一个此时还是可以用一个prufer序列与合法生成树对应，故方案数为\(n^{m-1}m^{n-1}\)

Tips:

一般要特判n=1的情况

Valuable Forests

大意：

定义一个树的权值为其所有节点的度数的平方和，森林的权值为所有树的权值和。求大小为n的所有有标号森林的权值和

思路：

\(f_i\)表示大小为i的所有有标号森林的权值和，也就是答案

考虑对于最后一个点所在的树的大小为k的情况

则\(f_n=\sum_{k=1}^{n}\binom{n-1}{k-1}f_{n-k}m_k+\binom{n-1}{k-1}g_kh_{n-k}\)

其中\(m_i\)表示大小为\(i\)的有标号无根树的个数，\(g_i\)表示大小为\(i\)的所有有标号无根树的权值和，\(h_{n-k}\)表示大小为\(n-k\)的森林的数量。\(\binom{n-1}{k-1}\)是因为枚举的k的含义是n所在树的大小，我要从剩下\(n-1\)个点里面选\(k-1\)个点。如果不这样枚举的树的组合就会算重。

\(m_n\)很简单：\(n=1\)时\(m_1=1\)，否则\(m_n=n^{n-2}\)

对于\(g_n\),我们枚举所有度数为i的贡献

转化到prufer序列中看这个问题，度数为i，表示出现了\(i-1\)次，所以强制选定对应的数字以及位置，剩下的\(n-1\)个数随便放

\(g_n=\sum_{i=1}^{n-1}i^2n\binom{n-2}{i-1}{n-1}^{n-1-i}\)

\(h_n\)的更新思路和\(f\)差不多，枚举最后一个点所在的树的大小即可

\(h_n=\sum_{i=1}^{n}\binom{n-1}{i-1}h_{n-i}m_i\)

cf 156D

大意：

给定n个点以及m条连边，记最少添加T条边使得整张图连通，问有多少种恰好添加T条边的方案使得图连通

思路:

记当前连通块个数为k，则T=k-1

对于每一个连通块，其大小为\(a_i\)，如果其度数为\(d_i\)的话，我们可以在以连通块为单位的情况下得到生成树个数为\(\binom{k-2}{d1-1,d2-1...d_k-1}\)

对于每一个连通块，固定连边的标号顺序（比如第1条边来自标号最小的连通块，依次类推），那么此时总方案数为\(\binom{k-2}{d1-1,d2-1...d_k-1}*\prod_{i=1}^{k}a_i^{d_i}\),因为每一条边都可以有\(a_i\)种选择

所以答案为\(\sum_{\sum d_i=k-2}\binom{k-2}{d1,d2...d_k}*\prod_{i=1}^{k}a_i^{d_i+1}=\sum_{\sum d_i=k-2}\frac{(k-2)!}{\prod_{i=1}^{k} d_i!}*\prod_{i=1}^{k}a_i^{d_i+1}=(k-2)!\prod_{i=1}^{k} a_i(\sum_{\sum_{i=1}^{k} d_i=k-2}\prod_{i=1}^{k}\frac{a_i^{d_i}}{d_i!})\)

注意到\((k-2)!\prod_{i=1}^{k} a_i\)是一个常数，我们只用看后面

记生成函数\(f_x=\sum_{i=0}^{\inf}\frac{x_i}{i!}=e^x\)

不难发现后面其实是k个函数\(f_{a_i}\)的卷积的某一项,故最终答案为\([x^{k-2}]\prod_{i=1}^{k}e^{a_ix}=[x^{k-2}]e^{nx}=\frac{n^{k-2}}{(k-2)!}\)

所以最终答案为\(n^{k-2}\prod_{i=1}^{k}a_i\)

LGV引理

在一个有向无环图G中，出发点\(A=\{a_1,a_2,...a_n\}\)，目标点\(B=\{b_1,b_2,..b_n\}\)。有向边\(e\)的权值为\(w_e\)，\(e(u,v)\)为路径边权乘积之和，即\(e(u,v)=\sum_{P:a->b}\prod_{e\in P}w_e\)

则\(\begin{vmatrix} e(a_1,b_1)& e(a_1,b_2) & ... & e(a_1,b_n)\\ e(a_2,b_1)& e(a_2,b_1) & ... & e(a_2,b_n)\\ ...& ... & & ...\\ e(a_n,b_1)& e(a_n,b_2) & ... & e(a_n,b_n) \end{vmatrix}=\sum_{S:A->B}(-1)^{N(\sigma)}\prod_{i=1}^n\prod_{e\in S_i}w_e\)

其中\(\sigma\)是一个n元置换，\(N(\sigma)\)表示逆序对个数,\(S_i:a_i->b_i\)是一组A到B的不相交路径。

此处的不相交是指处处不存在相同的点在两条路径中同时存在，起终点也不行，所以A里的元素互不相同。如果初始条件并非如此，可能要转化一下

在算法竞赛中，该引理在普通的DAg下没有过多的用处，因为其右式还是过于复杂。但是如果图满足所有边权为1（这样\(e(u,v)\equiv1\),就可以表示路径数量了），并且只存在唯一的一个$\(满足所有\)a_i->b_i$不相交的话，此时右式只有一个因子，含义就是整张图的不相交路径组数，就可以用左式的行列式表示了

Monotonic Matrix

大意：

\(A_1(1,0),A_2(0,1),B_1(n,m+1),B_2(n+1,m)\),求\(A_1->B_1,A_2->B_2\)的不相交路径数。其中每一步只能向上/向右

套板子即可

#include <bits/stdc++.h>
#define pii pair<int,int>
#define il inline
#define ll long long
using namespace std;
const int N=2010;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m;
ll c[N][N];
void init(ll n)
{
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<=i;++j)
        {
            if(j==0) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
}
ll f(ll x1,ll y1,ll x2,ll y2)
{
    //(x1,y1)->(x2,y2)
    ll len1=x2-x1;
    ll len2=y2-y1;
    return c[len1+len2][len2];
}
void solve()
{
    // cin>>n>>m;
    ll a=f(0,1,n,m+1)*f(1,0,n+1,m)%mod;
    ll b=f(0,1,n+1,m)*f(1,0,n,m+1)%mod;
    cout<<((a-b)%mod+mod)%mod<<endl;
}
int main()
{
//     freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    init(2005);
    while(cin>>n>>m)
    // ll t;cin>>t;while(t--)
    solve();
    return 0;
}