首页 > 其他分享 >Prüfer 序列 学习笔记

Prüfer 序列 学习笔记

时间:2024-06-06 10:45:00浏览次数:18  
标签:Pr limits int 笔记 fer 序列 prod

引入

Prüfer 序列可以用于求解序列与树的双射,常用于组合计数问题。

定义

Prüfer 序列指的是每次选取一个编号最小的叶子,删除它,然后在序列中记录它所链接的点,重复以上步骤直到只剩下两个节点。

过程

对树建立 Prüfer 序列

显然可以用堆实现一个朴素的 \(\mathcal{O}(n \log n)\) 算法。

但是,效率太低了,其实还存在一个线性的算法。

线性建立 Prüfer 序列

可以发现,每删除一个叶子节点,叶子节点的数量最大增加一个,即叶子节点的数量是非严格单调递减的。

那么可以维护一个指针 \(p\),指向当前编号最小的节点,执行以下操作:

  1. 删除当前节点 \(p\),然后检查是否出现新的叶子节点。
  2. 如果出现新的叶子节点 \(x\),如果 \(x < p\) 立刻将 \(x\) 删除,并执行 \(1\) 步骤,否则跳过不管。
  3. 重复以上操作,知道只剩下两个点。

正确性显然,因为每个点如果小于 \(p\),那么会立刻删除,否则之后肯定会访问到它。

复杂度分析,可以发现每条边最多删除一次,因此时间复杂度显然\(\mathcal{O}(n)\)。

性质

  1. 根据上述过程,显然 \(n\) 号节点永远不可能删除。
  2. 每个点出现次数是其度数减一。

通过 Prüfer 序列建立树

根据 Prüfer 序列的性质可以知道每个点的度数,然后可以知道当前编号最小的节点,它必然和现在的序列的第一个数相连,然后同时删除这两个点,最后重复以上步骤就可以得到树,最后再连上剩下的两个节点即可。

这个方法使用堆显然可以 \(\mathcal{O}(n \log n)\) 解决。

但是同样的它还存在一个线性做法

线性建树

同样的维护一个指针 \(p\)。

然后利用建立 Prüfer 序列的过程的思路,就可以实现 \(\mathcal{O}(n)\) 建树。

实现

以下是【模板】Prufer的代码。

#include <cstdio>
#include <vector>
#include <algorithm>

using u32 = unsigned int ;
using i64 = long long ;
using u64 = unsigned long long ;

const int N = 5e6 + 5;

// -------------------- 快读
bool isdigit(int __C){return '0'<=__C&&__C<='9';}
char *p1,*p2,buf[1<<20];
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<typename _Tp>
void read(_Tp & x) {
    x = 0;
    int fh = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();}
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    x *= fh;
}

template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...args){
    read(x), read(args...);
}
// ---------------------- end

int n, m;
int f[N], p[N];
int deg[N];

std::vector<int> GetPrufer(){
    int p = -1;
    for (int i = 1; i < n; i++) {
        if (deg[i] == 1) {
            p = i;
            break;
        }
    }

    std::vector<int> code(n - 2);
    int leaf = p;

    for (int i = 1; i <= n - 2; i++) {
        int nxt = f[leaf];
        code[i - 1] = nxt;

        if (--deg[nxt] == 1 && nxt < p) {
            leaf = nxt;
        } else {
            ++p;
            while (deg[p] != 1) {
                ++p;
            }

            leaf = p;
        }
    }

    return code;
}

std::vector<int> build(){
    int ptr = -1;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            ptr = i;
            break;
        }
    }

    std::vector<int> tree(n);
    int leaf = ptr;
    
    for (int i = 1; i <= n - 2; i++) {
        int v = p[i];
        tree[leaf] = v;

        if (--deg[v] == 1 && v < ptr) {
            leaf = v;
        } else {
            ++ptr;
            while (deg[ptr] != 1) {
                ++ptr;
            }

            leaf = ptr;
        }
    }

    tree[leaf] = n;
    return tree;
}

i64 ans;
int main(){
    read(n, m);

    if (m == 1) {
        for (int i = 1; i < n; i++) {
            read(f[i]);
            deg[i]++, deg[f[i]]++;
        }
        
        auto code = GetPrufer();

        for (int i = 0; i < n - 2; i++) {
            ans ^= (1ll * (i + 1) * code[i]);
        }
    } else {
        for (int i = 1; i <= n; i++) {
            deg[i] = 1;
        }

        for (int i = 1; i <= n - 2; i++) {
            read(p[i]);
            deg[p[i]]++;
        }
        
        auto tree = build();

        for (int i = 1; i < n; i++) {
            ans ^= (1ll * i * tree[i]);
        }
    }

    printf("%lld", ans);
    return 0;
}

凯莱定理

定理

对于一个完全图 \(K_n\) 它的生成树个数为 \(n ^ {n - 2}\) 。

证明

可以通过构造 Prüfer 序列证明,因为是完全图,所以对于任意一个长度为 \(n - 2\) 的序列都能构成一个生成树,因此得证。

拓展

图联通方案

问题

给定一个 \(n\) 个点 \(m\) 条边的 \(k\) 个连通块,要求添加 \(k - 1\) 条边,使得图联通,求方案数。

记号说明

记 \(s_i\) 表示第 \(i\) 个连通块大小, \(d_i\) 为连接后第 \(i\) 个联通块作为树上一个顶点的的度数,因此有 \(\sum\limits_{i = 1}^k d_i = 2k -2\)。

结论

\(\text{方案数} = n ^{k - 2} \prod\limits_{i = 1}^k s_i\)

证明

先对给定的 \(d_i\) 构造 Prüfer 序列,它的方案数有:

\[\frac{(k - 2) !}{\prod\limits_{i = 1} ^ n (d_i - 1) !} \]

然后对于每个联通块内部有 \(s_i^{d_i}\) 种方案(考虑没条边连向哪个点),还要枚举每个联通块的度数,因此总的方案有:

\[\sum\limits_{d_i > 0 , \sum\limits_{i = 1} ^ n d_i = 2k - 2}\frac{(k - 2) !}{\prod\limits_{i = 1} ^ n (d_i - 1) !} \prod\limits_{i = 1} ^ k s_i^{d_i} \]

这个式子貌似化简不了了,但是还有一个多元二项式定理可以化简它。

多元二项式定理

\[(x_1 + x_2 + \cdots + x_n) ^ m = \sum\limits_{c_i > 0,\sum\limits_{i = 1} ^ n c_i = m} \frac{m !}{\prod\limits_{i = 1} ^ n (c_i - 1) !} \prod_{i = 1} ^ n x_i ^ {c_i} \]

因此可以设 \(e_i = d_i - 1\),那么有 \(\sum e_i =k - 2\)。

因此原式可以化为:

\[\sum\limits_{d_i > 0 , \sum\limits_{i = 1} ^ n e_i = k - 2}\frac{(k - 2) !}{\prod\limits_{i = 1} ^ n e_i !} \prod\limits_{i = 1} ^ k s_i^{e_i + 1} \]

可以化简为:

\[(s_1 + s_2 + \cdots + s_k) ^ {k - 2} \prod_{i = 1} ^ k s_i \]

也就是:

\[n^{k - 2} \prod_{i = 1} ^ k s_i \]

标签:Pr,limits,int,笔记,fer,序列,prod
From: https://www.cnblogs.com/zdrj/p/18234670

相关文章

  • Spring Boot中集成ActiveMQ(九)
    SpringBoot中集成ActiveMQ:全面指南......
  • Vue学习笔记_Day01
    文章目录1,入门案例2,双大括号3,响应式特性4,安装浏览器插件5,指令v-html6,v-show和v-if7,v-else和v-else-if8,v-on9,v-bind10,v-for11,v-model1,入门案例第一步,导入Vue库。<scriptsrc="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script>第二步,准备DOM,我们称之为模......
  • 界面组件DevExpress Reports v23.2增强用户体验 - 轻松导航Web设计器
    DevExpressReporting是.NETFramework下功能完善的报表平台,它附带了易于使用的VisualStudio报表设计器和丰富的报表控件集,包括数据透视表、图表,因此您可以构建无与伦比、信息清晰的报表。DevExpressReportsv23.2(我们最近的主要更新)包含了对DevExpressWeb报表设计器的智能......
  • provide inject vue3 父子组件 传参方式
    provideinjectvue3父子组件传参方式当子组件有30个的时候,这个就有优势了,在父组件provide一次,在子组件里面inject这个变量(实际上是通过hooks提供,也可以是个函数)。下面看下截图父组件:子组件:父组件provide子组件在父组件,就不用一堆props这里有一个特别的好处就是结构......
  • Xshell或其他命令行终端中,提示符(prompt)中的主机名太长,影响视觉体验或阅读方便性
    如果在Xshell或其他命令行终端中,你发现提示符(prompt)中的主机名太长,影响视觉体验或阅读方便性,你可以通过修改Linux系统的配置来缩短或美化这个提示符。这里有两种方法来解决这个问题:###1.暂时修改提示符你可以在当前终端会话中临时改变提示符,这不会影响其他用户或重启后的设置。......
  • 基于springboot实现餐饮管理系统项目【项目源码+论文说明】计算机毕业设计
    基于springboot实现餐饮管理系统演示摘要互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱,出错率高,信息安全性差,劳动强度大,费时费力等问题,采用餐......
  • 基于springboot实现社区养老服务系统项目【项目源码+论文说明】计算机毕业设计
    基于springboot实现社区养老服务系统演示摘要现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本社区养老服务系统就是在这样的大环境下诞生,其可以帮助使用者在短时间内处理完毕庞大的数据信息,使用这......
  • 基于springboot实现小区团购管理系统项目【项目源码+论文说明】计算机毕业设计
    基于springboot实现小区团购管理系统演示摘要传统办法管理信息首先需要花费的时间比较多,其次数据出错率比较高,而且对错误的数据进行更改也比较困难,最后,检索数据费事费力。因此,在计算机上安装小区团购管理软件来发挥其高效地信息处理的作用,可以规范信息管理流程,让管理工作......
  • 毕业设计-基于Springboot+Vue的幼儿园管理系统的设计与实现(源码+LW+包运行)
    如需完整项目,请私信博主基于SpringBoot+Vue的幼儿园管理系统 开发语言:Java数据库:MySQL技术:SpringBoot+MyBatis+Vue.js工具:IDEA/Ecilpse、Navicat、Maven在当今高度发达的信息中,信息管理改革已成为一种更加广泛和全面的趋势。“幼儿园管理系统”是基于Mysql数据库,在SpringB......
  • 毕业设计-基于Springboot+Vue的在线动漫信息平台 的设计与实现(源码+LW+包运行)
    如需完整项目,请私信博主基于SpringBoot+Vue的在线动漫信息平台 开发语言:Java数据库:MySQL技术:SpringBoot+MyBatis+Vue.js工具:IDEA/Ecilpse、Navicat、Maven目 录第一章绪论1.1背景及意义11.2国内外研究概况21.3研究的内容2第二章 关键技术的研究2.1B/S架......