当前位置: 首页 > news >正文

【笔记】Prfer 序列

之前的版本

观前提示:可以用 alt+0252 打出来 ü 这个字符喵

1. 对树建立 Prüfer 序列

\(\rm Def.\) Prüfer 序列的构建如下:
每次选择树中编号最小的叶节点并删去它,并在一个初始为空的序列末加入其连接到的节点,直到整个树剩下 \(2\) 个节点(即 Prüfer序列 的长度为 \(n-1\)

实现

首先可以用堆,这显然是 \({\cal O}(n \log n)\) 的。

不过 Prüfer 序列也可以线性构造,过程:
0. 用一个指针 \(p\) 指向编号最小的叶节点;

  1. 删除 \(p\) 指向的节点;
  2. 如果产生新的叶节点,且编号小于原节点,删除之,并重复本步;
  3. \(p\) 自增,直至指向一个未被删除的叶节点。
    这个算法的正确性是有保证的,因为每次删除的一定是最小的叶节点。第 2 步中产生的新的叶结点中编号大于原节点的一定会在之后被扫描到。
    时间复杂度上,\(p\) 至多自增 \(n-1\) 次,而第二步产生新的叶节点一定会消耗边,一棵树只有 \(n-1\) 条边,故总的时间复杂度是 \({\cal O}(n)\) 的。

2. 性质

  1. 最后剩下俩节点,其中必有 \(n\)
  2. 每个节点 \(v\) 出现 \({\rm deg}(v)-1\) 次。

3. 用 Prüfer 序列重构树

用 Prüfer 序列还原整棵树上节点的度数,找到序号最小的叶节点,prüfer 序列的第一个元素就是它的父节点。之后将它的父节点度数减一,继续之前的过程。

用堆维护,是 \({\cal O}(n \log n)\) 的。

重构也有线性的算法,和 [[Prüfer序列#实现|对树建立 Prüfer 序列的线性算法]] 如出一辙。

4. 代码

P6086 【模板】Prufer 序列

\({\cal O}(n \log n)\) 实现

void PtT() {for(int i = 1;i <= n-2;++i) deg[a[i]]++;for(int i = 1;i <= n;++i) if(deg[i] == 0) q.push(i);for(int i = 1;i <= n-2;++i) {b[q.top()] = a[i];q.pop();if(--deg[a[i]] == 0) q.push(a[i]);}for(int i = 1;i <= n-1;++i) {if(b[i] == 0) b[i] = n;ans ^= 1ll*i*b[i];}
}
void TtP() {for(int i = 1;i < n;++i) {deg[i]++;deg[a[i]]++;}for(int i = 1;i <= n;++i) if(deg[i] == 1) q.push(i);for(int i = 1;i <= n-2;++i) {b[i] = a[q.top()];q.pop();if(--deg[b[i]] == 1) q.push(b[i]);ans ^= 1ll*i*b[i];}
}

傻逼浓缩

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n-m;++i)
        scanf("%d",&a[0][i]);
    if(m == 2)
        a[0][n-1] = n;
    for(int i = 1;i <= n-m;++i)
        deg[a[0][i]]++;
    for(int i = 1;i <= n;++i)
        if(deg[i] == 0)
            q.push(i);
    m--;
    for(int i[2] = {1,0};i[0] < n-(m^1);++i[0]) {
        i[1] = q.top();
        a[1][i[m]] = a[0][i[m^1]];
        ans ^= 1ll*i[m]*a[1][i[m]];
        q.pop()
        if(--deg[a[1][i[m]]] == 0)
            q.push(a[1][i[m]]);
    }
    printf("%lld\n",ans);
    return 0;
}

\({\cal O}(n)\) 实现

void TtP() {for(int i = 1;i < n;++i) deg[a[i]]++;for(int p = 1, i = 0;p < n;++p) {int q = p;while(!deg[q]) {b[++i] = a[q];deg[a[q]]--;if(a[q] > p) break;q = a[q];}}
}
void PtT() {a[n-1] = n;for(int i = 1;i < n;++i) deg[a[i]]++;for(int p = 1, i = 0;p < n;++p) {int q = p;while(!deg[q]) {b[q] = a[++i];deg[b[q]]--;if(b[q] > p) break;q = b[q];}}
}

5. 凯莱公式

由上述 [[Prüfer序列#1. 对树建立 Prüfer 序列|Part 1]] 和 [[Prüfer序列#3. 用 Prüfer 序列重构树|Part 3]],我们得到了一个大小为 \(n\) 的无根树与长为 \(n-2\) 的序列之间的一一对应,所以我们可以证明 Cayley 公式:

\[\text{完全图}\ K_n\ \text{有}\ n^{n-2}\ \text{棵生成树。} \]

http://www.hskmm.com/?act=detail&tid=16717

相关文章:

  • win11 无线投屏(Miracast:)引发的思考附带解决方案 - Popeye
  • 2025年十大主流项目管理工具评测:功能覆盖与成本效益分析
  • 关于MCO使用配置
  • 向量那点事儿
  • c++输入输出详解
  • docker/docker compose/k8s
  • 中国开发者迎来新选择:Gitee成为研发协作平台转型期的中流砥柱
  • RK3588-ubuntu server - 详解
  • 一文教你上手 Geometric Glovius 6.0:安装、授权与首个项目演示
  • 32单片机+free rtos移植CJSON库函数主要流程
  • Gitee如何重塑中国开发者生态:本土化创新与数字化转型的双重奏
  • 输入输出接口
  • Go语言中的信号捕获与优雅退出:SIGINT、SIGTERM和SIGKILL详解 - 若
  • (二)3.1.9 生产“稳”担当:Apache DolphinScheduler Worker 服务源码全方位解析
  • 完整教程:生产环境实战:Spring Cloud Sleuth与Zipkin分布式链路追踪实践
  • 训练“系统级思维”,听时序数据库 IoTDB Committer 说说从设计到应用的成长
  • 关于gradle项目启动
  • Day08
  • 常见闪存区别
  • 进程、线程、协程、虚拟线程,傻傻分不清楚
  • 事倍功半是蠢蛋55 ctrl+shift+f 每次搜索都按倒繁体
  • Ini文件的读写
  • 数据跨境传输解决方案助力企业安全合规高效流通
  • 题解:P9454 [ZSHOI-R1] 巡城
  • QuestaSim奔溃后再次打开无法仿真
  • 软考架构备考-软件可靠性、知识产权和标准化
  • 医院内外网文件传输:平衡安全与效率的关键链路!
  • 我的第一个赚钱网站 -- 从网站源码到集成AdSense获利的全过程
  • Gradle读取仓库配置文件的优先级
  • opencv学习记录5