Prufer序列

lao_li · 2022-07-28 11:03:29 · 个人记录

对于一棵有n个点，每个点有标号的无根树，我们定义一个Prufer序列与之对应，方便起见，不妨先假设其根为n。具体构造为：找到标号最小的叶子节点，将其从树上删去并将其父亲放入Prufer序列，直到只剩两个点时停止。

指定一个Prufer序列，也可据此构造唯一的树：根据Prufer序列得到每个点的度数，先在prufer序列末尾添加一项n。枚举一个指向Prufer序列的递增的指针i，再找到编号最小的叶子节点（度为1），将其父亲设为当前指针，将两个点的度都-1。不难发现，根据Prufer序列构造树其实是构造Prufer序列的可逆过程，也就是说实质上是在对树删点。那么下一个可能的儿子可能是当前i指向的点，其父亲可能就是Prufer序列的下一项，也就是不断向上跳，i不断自增直到p[i]<=j为止。

两种操作都可以做到O(n)。

P6086 【模板】Prufer 序列

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const int MAXN=5e6+5;
int n,m;
int a[MAXN],b[MAXN];
int d[MAXN];
ll ftop(){
    rep(i,1,n-1)d[a[i]]++;
    for(int i=1,j=1;i<=n-2;i++,j++){
        while(d[j])j++;
        b[i]=a[j];
        while(i<=n-2&&!--d[b[i]]&&b[i]<j)b[i+1]=a[b[i]],i++;
    }
    ll res=0;
    rep(i,1,n-2)res^=ll(i)*ll(b[i]);
    return res;
}
ll ptof(){
    rep(i,1,n-2)d[a[i]]++;
    a[n-1]=n;
    for(int i=1,j=1;i<=n-1;i++,j++){
        while(d[j])j++;
        b[j]=a[i];
        while(i<=n-1&&!--d[a[i]]&&a[i]<j)b[a[i]]=a[i+1],i++;
    }
    ll res=0;
    rep(i,1,n-1)res^=ll(i)*ll(b[i]);
    return res;
}
int main(){
    read(n),read(m);
    rep(i,1,n-2)read(a[i]);
    if(m==1){
        read(a[n-1]);
        printf("%lld\n",ftop());
    }
    else printf("%lld\n",ptof());
    return 0;
}

性质

Prufer序列长度为n-2。
不难发现，若指定一个点为根，对于每个点，其在Prufer序列中出现的次数是其儿子个数，所以每个点出现次数为该点度数-1，没有出现的就是叶子。
Prufer序列和树构成一个双射。也就是说任意一个树都有唯一的Prufer序列，而任意一个Prufer序列都有唯一的树与之对应。

应用

由于Prufer序列和树构成一个双射，常用于解决和树的度数有关的计数问题。

克莱定理

对于有标号的n个点的无向完全图，其无根生成树个数为n^{n-2}。
考虑其Prufer序列，每个位置有n种选择，可以构造n^{n-2}个Prufer序列，而任意一个Prufer序列都能对应到一个生成树。
UVA10843 Anne's game

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const ll mod=2000000011;
int n;
ll ksm(ll a,ll e){
    ll res=1;
    while(e>0){
        if(e&1)res=(res*a)%mod;
        a=(a*a)%mod;
        e>>=1;
    }
    return res;
}
int main(){
    read(n);
    rep(i,1,n){
        ll x;
        read(x);
        printf("Case #%d: %lld\n",i,ksm(x,x-2));
    }
    return 0;
}

杂题

P2290 [HNOI2004]树的计数
给出每个点的度数，求满足情况的有几种无根树。
根据排列组合相关，可以知道是\Large \frac{(n-2)!}{\Pi(d_i-1) }。注意特判无解，如果\Sigma(d_i-1) \neq n-2显然为0。防止中途答案爆范围，用质因数分解。

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const int MAXN=155;
int n,d[MAXN];
int p[MAXN][MAXN],p1[MAXN],p2[MAXN];
ll ksm(ll a,int e){
    ll res=1LL;
    while(e){
        if(e&1)res*=a;
        a*=a;
        e>>=1;
    }
    return res;
}
int main(){
    read(n);
    int s=0;
    rep(i,1,n){
        read(d[i]);
        if(d[i]<=0&&n!=1){puts("0");return 0;}
        s+=d[i];
    }
    if(s!=2*n-2){puts("0");return 0;}
    if(n<=2){puts("1");return 0;}
    rep(i,2,n-2){
        int t=i,END=sqrt(i);
        rep(j,2,END)
            while(t%j==0){
                p[i][j]++;
                t/=j;
            }
        if(t>1)p[i][t]++;
    }
    rep(i,2,n-2)
        rep(j,2,i)p1[j]+=p[i][j];
    rep(i,1,n)
        rep(j,2,d[i]-1)
            rep(k,2,j)p2[k]+=p[j][k];
    ll ans=1LL;
    rep(i,2,n-2)ans*=ksm(ll(i),p1[i]-p2[i]);
    printf("%lld\n",ans);
    return 0;
}

CF156D Clues
给定一个 n 个点 m 条边的带标号无向图，它有 k 个连通块，求添加 k-1 条边使得整个图连通的方案数，答案对 p 取模。

前置知识：多项式定理，即二项式定理的拓展版。
先定义一个记号\binom{n}{n_1,n_2...n_k}=\frac{n!}{n_1!n_2!...n_k!}

那么多项式定理就是\large (x_1+x_2+x_3+...+x_k)^n=\sum\limits_{n_i\geq 0,n_1+n_2+...+n_k=n}\binom{n}{n_1,n_2...n_k}\Pi x_i^{n_i}
回到这道题。
设每个连通块大小为s_i。将每个连通块缩成一个点，发现其度数并不确定，考虑枚举其度数序列d，答案为\sum\limits_{d_i\geq 1,d_1+d_2+...+d_k=2k-2}\binom{k-2}{d_1-1,d_2-1...d_k-1}\Pi s_i^{d_i}

设e_i=d_i-1，

化为\sum\limits_{e_i\geq 0,e_1+e_2+...+e_k=k-2}\binom{k-2}{e_1,e_2...d_k}\Pi s_i^{e_i+1}

利用多项式定理， (s_1+s_2+...+s_k)^{k-2}\Pi s_i

即n^{k-2}\Pi s_i

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=1e5+5;
typedef long long ll;
int n,m,p,k;
int fa[MAXN],sz[MAXN];
int FIND(int x){
    return x==fa[x]?x:fa[x]=FIND(fa[x]);
}
void meg(int x,int y){
    int fx=FIND(x),fy=FIND(y);
    fa[fy]=fx;
}
ll ksm(ll a,int e){
    ll res=1;
    while(e){
        if(e&1)res=(res*a)%p;
        a=(a*a)%p;
        e>>=1;
    }
    return res;
}
int main(){
    read(n),read(m),read(p);
    rep(i,1,n)fa[i]=i;
    int x,y;
    rep(i,1,m){
        read(x),read(y);
        meg(x,y);
    }
    rep(i,1,n)sz[FIND(i)]++;
    ll ans=1;
    rep(i,1,n)
        if(FIND(i)==i)k++,ans=(ans*sz[i])%p;
    if(k==1){printf("%d\n",1%p);return 0;}
    ans=(ans*ksm(n,k-2))%p;
    printf("%lld\n",ans);
    return 0;
}