【图论】树剖(上):重链剖分

devtools/2024/10/9 10:36:53/

一、前置知识清单

  1. 深度优先搜索DFS 点我复习
  2. 图的存储 复习链接敬请期待
  3. 树状数组 点我复习

二、树剖简介

树剖(树链剖分),是一种把树划分成链的算法,该算法分为重链剖分和长链剖分。
本文仅讨论重链剖分,长链剖分目前本人还不会,所以不予展示。

三、模拟重链剖分

图6是一棵树,我们钦定1号结点为根。
图6
图6

若要对这棵树进行重链剖分,首先要求出它的DFN序。注意这里的DFN序与DFS序还是有一定区别的。 DFN序就是优先遍历每个结点重儿子的DFS序。
以上面的图6为例,我们先求出以每个结点为根的子树重量 s i z i siz_i sizi(即以每个结点为根的子树所包含的结点个数)。该树中 s i z i siz_i sizi 分别等于 5 5 5 2 2 2 1 1 1 4 4 4 1 1 1
对于每个非叶子结点,找到其 s i z i siz_i sizi 最大的儿子(即重儿子),记为 s o n i son_i soni。若有多个儿子的 s i z i siz_i sizi 相等,则 s o n i son_i soni 取任意一个儿子均可。该树中 s o n i son_i soni 分别等于 4 4 4 3 3 3 0 0 0 2 2 2 0 0 0
我们将每个重儿子和它的父亲连接,形成一条条重链。该树中有两条重链: 1 1 1 4 4 4 2 2 2 3 3 3 为一条重链, 5 5 5 自成一条重链。

四、代码实现重链剖分

感谢@xixisuper_提供树剖代码。由于本人一顿操作,代码变得又长又唐,请见谅。

#include<bits/stdc++.h>
using namespace std;
vector<int>e[114514];
int fa[114514],dep[114514],siz[114514],son[114514];
//fa[i]存储每个非根节点的父亲,dep[i]存储每个结点的深度 
void dfs(int u,int father){int lz;fa[u]=father;dep[u]=dep[father]+1;siz[u]=1;lz=e[u].size();for(int i=0;i<lz;i++){if(e[u][i]==father)continue;//避免回搜 dfs(e[u][i],u);//本人的十手笔记本电脑写了auto会编译错误 siz[u]+=siz[e[u][i]];if(siz[son[u]]<siz[e[u][i]]) son[u]=e[u][i];}
}//找重儿子 
int dfn[114514],nidfn[114514],top[114514],tot;
//dfn[i]存储DFN序(点到下标),nidfn[i]存储逆DFN序(下标到点),你只需要知道这两个东西很有用就行了 
//top[i]存储链顶 
void pf(int u,int father){int lz; dfn[u]=++tot; nidfn[tot]=u;if(son[u]){top[son[u]]=top[u];pf(son[u],u);//先遍历重儿子 }lz=e[u].size();for(int i=0;i<lz;i++){if(e[u][i]==father)continue;//避免回搜 if(e[u][i]==son[u])continue;//重儿子已经遍历过了 top[e[u][i]]=e[u][i];pf(e[u][i],u);}
}//剖分,求DFN序 
int lowbit(int x){return x&(-x);
}
struct st{//使用树状数组维护区间和 int c[114514];void add(int x,int y){for(int i=x;i<=y;i+=lowbit(i))c[i]+=y;//单点修改 return;}void add(int x,int y,int z){for(int i=x;i<=y;i++)add(i,z);//这里的区间修改貌似有点怪怪的,有什么可以优化的地方请私信我,备注142719158return; }int query(int x){int r=0;//前缀查询for(int i=x;i;i-=lowbit(i))r+=c[i];return r;}int query(int x,int y){return query(y)-query(x-1);//区间查询 }
}tr;
void update(int x,int y,int z){//将x与y之间唯一路径上的点点权加上zwhile(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]]){tr.add(dfn[top[x]],dfn[x],z);//当两个结点不在同一条链上时,深度更大的结点向上跳 x=fa[top[x]];//向上跳到链顶的父亲 }else{tr.add(dfn[top[y]],dfn[y],z);y=fa[top[y]];//向上跳到链顶的父亲 }}if(dep[x]>dep[y])tr.add(dfn[y],dfn[x],z);else tr.add(dfn[x],dfn[y],z);return; 
}
int qry(int x,int y){//查询x与y之间唯一路径上的点点权之和 int r=0; while(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]]){r+=tr.query(dfn[top[x]],dfn[x]);//当两个结点不在同一条链上时,深度更大的结点向上跳 x=fa[top[x]];//向上跳到链顶的父亲 }else{r+=tr.query(dfn[top[y]],dfn[y]);y=fa[top[y]];//向上跳到链顶的父亲 }}if(dep[x]>dep[y])r+=tr.query(dfn[y],dfn[x]);else r+=tr.query(dfn[x],dfn[y]);return r;
}
int main(){dfs(1,0);top[1]=1;pf(1,0);return 0;
}

如果博客有错误,或者发现了代码中的问题,请联系我,备注142719158,我会尽快修正!鲁A济南车!


http://www.ppmy.cn/devtools/123331.html

相关文章

BUU刷题-Pwn-shanghai2018_baby_arm(ARM_ROP_csu_init,ARM架构入门)

解题思路&#xff1a; 泄露或修改内存数据&#xff1a; 堆地址&#xff1a;无需栈地址&#xff1a;无需libc地址&#xff1a;无需BSS段地址&#xff1a;无需 劫持程序执行流程&#xff1a;ARM_ROP && mprotect函数(运行内存权限修改) && [[ARM_ROP_csu_init]…

vue 不是spa 单页面应用吗? 配置路由工作模式为history 后 ,为什么配置Nginx的 try_files 可以根据url 找到对应的文件?

免责申明 记录用&#xff0c;本人主要是后端,可能理解有误 Vue.js 是一个前端框架&#xff0c;主要用于构建单页面应用程序&#xff08;SPA&#xff09;。然而&#xff0c;Nginx 是一个服务器端的应用程序&#xff0c;负责处理 HTTP 请求并返回相应的资源。 当在 Vue.js 应用…

【k8s深入理解之csi插件】理解存储 csi 插件的总体逻辑框架

转载自 k8s通过ceph-csi接入存储的概要分析 - 良凯尔 - 博客园如何接入 K8s 持久化存储&#xff1f;K8s CSI 实现机制浅析 - 腾讯云原生 - 博客园29 | PV、PVC体系是不是多此一举&#xff1f;从本地持久化卷谈起-深入剖析 Kubernetes-极客时间K8S-StorageClass资源-实践【补充…

Python机器学习框架介绍和入门案例:Scikit-learn、TensorFlow与Keras、PyTorch

Python机器学习框架介绍和入门案例 目录 &#x1f31f; 机器学习框架概述&#x1f4ca; Scikit-learn 2.1 模型选择与评估2.2 常用API&#xff08;fit、predict、score&#xff09;2.3 实现示例&#xff08;线性回归、K近邻&#xff09; &#x1f680; TensorFlow与Keras 3.1…

LC538 - 把二叉搜索树转换为累加树

文章目录 1 题目2 思路3 ACM模式参考 1 题目 https://leetcode.cn/problems/convert-bst-to-greater-tree/description/ 给出二叉 搜索 树的根节点&#xff0c;该树的节点值各不相同&#xff0c;请你将其转换为累加树&#xff08;Greater Sum Tree&#xff09; 累加树&#…

KiCad 综合笔记

开窗 选中顶层或者底层 Mask 层&#xff0c;然后进行覆铜&#xff1a; 四层板 KiCad Tutorial - How to make a 4 layer PCB https://bbs.elecfans.com/jishu_2365544_1_1.html 虽然在“电路板设置”中&#xff0c;可以选择铜层的类型&#xff0c;但如果选择了“电源层”&am…

攻防世界----->Replace

前言&#xff1a;做题笔记。 下载 查壳。 upx32脱壳。 32ida打开。 先运行看看&#xff1a; 没有任何反应&#xff1f; 猜测又是 地址随机化(ASLR)---遇见过。 操作参考&#xff1a; 攻防世界----&#xff1e;Windows_Reverse1_dsvduyierqxvyjrthdfrtfregreg-CSDN博客 然后…

中国通信技术革命史

文章目录 引言I 中国通信技术革命史电报中国卫星通信的历史固定电话寻呼机(BP机)大哥大(手机)制定自己的移动通信网络技术体系5G未来科技发展的总趋势:用更少的能量,传输、处理和存储更多的信息II 知识扩展通信史(单位能量的信息传输率越来越高,网络地不断融合。)超级智能…