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

【图论】虚树 - 模板总结

适用于解决一棵树中只需要用到少部分点的时候,将需要用到的点提出来单独建一棵树

/********************* 虚树 *********************/
struct edge
{int to, next;int val;
};struct Virtual_Tree
{int n; // 点数int dfn[N]; // dfs序int dep[N]; // 深度int fa[N][25], m[N];int num; // 关键点数vector<int> lst; // 关键点bool query[N]; // 是否为关键点int top, cnt1 = 1, cnt2 = 1, dfscnt = 1;int stk[MAXN];int head1[N], head2[N];struct edge edge1[N << 1], edge2[N << 1]; // 原树和虚树/* 在下方添加需要的信息定义 */int minv[N];/***************************/// 初始化void init(){for (int i = 1; i <= n; i ++ ){dfn[i] = dep[i] = m[i] = query[i] = 0;for (int j = 0; j < 24; j ++ ) fa[i][j] = 0;}}// 原树建边void add1(int x, int y, int v){edge1[cnt1].next = head1[x];edge1[cnt1].to = y;edge1[cnt1].val = v;head1[x] = cnt1 ++ ;}// 虚树建边void add2(int x, int y){edge2[cnt2].next = head2[x];edge2[cnt2].to = y;head2[x] = cnt2 ++ ;}// 预处理原树基本信息void dfs1(int pos){int k;for (k = 0; fa[pos][k]; k ++ ) fa[pos][k + 1] = fa[fa[pos][k]][k];m[pos] = k;dfn[pos] = dfscnt++;for (int i = head1[pos]; i; i = edge1[i].next){int to = edge1[i].to;if (!dfn[to]){dep[to] = dep[pos] + 1;fa[to][0] = pos;/* 在下方处理需要的信息 */minv[to] = min(minv[pos], edge1[i].val);/***********************/dfs1(to);}}}// 倍增求lcaint lca(int x, int y){if (dep[x] < dep[y]) swap(x, y);for (int i = m[x]; i > -1; i -- ){if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];}if (x == y) return x;for (int i = m[x]; i > -1; i -- ){if (fa[x][i] != fa[y][i]){x = fa[x][i];y = fa[y][i];}}return fa[x][0];}// 建虚树 关键点存在lst里 lst大小为k 下标从0开始void build(int k, vector<int>& lst){// 按照dfs序排序规则auto cmp = [&](int x1, int x2){return dfn[x1] < dfn[x2];};sort(lst.begin(), lst.end(), cmp);stk[top = 1] = lst[0];for (int i = 1; i < k; i ++ ){int now = lst[i];int lc = lca(now, stk[top]);while (1){if (dep[lc] >= dep[stk[top - 1]]){if (lc != stk[top]){add2(lc, stk[top]);if (lc != stk[top - 1]) stk[top] = lc;else top -- ;}break;}else{add2(stk[top - 1], stk[top]);top -- ;}}stk[++ top] = now;}while (-- top) add2(stk[top], stk[top + 1]);}// 树形dp计算答案int dfs2(int u){/* 下方填写计算答案代码逻辑 *//**************************/// 清空虚树query[u] = false;head2[u] = 0;return res;}// 在下方填写解题逻辑void solve(){/* 思路 *//********/// 每次建虚树后需要清空cnt2 = 1;lst.clear();}
} vtr;
/***********************************************/
http://www.lryc.cn/news/431597.html

相关文章:

  • [C#学习笔记]注释
  • c# checkbox的text文字放到右边
  • 【node.js】基础之修改文件
  • Notepad++回车不自动补全
  • CSS线性渐变拼接,一个完整的渐变容器(div),要拆分成多个渐变容器(div),并且保持渐变效果一致
  • 【60天备战软考高级系统架构设计师——第十天:软件设计与架构综合练习】
  • 2024.8.15(python管理mysql、Mycat实现读写分离)
  • CMU 10423 Generative AI:lec2
  • 恋爱相亲交友系统源码原生源码可二次开发APP 小程序 H5,web全适配
  • OceanBase 4.x 存储引擎解析:如何让历史库场景成本降低50%+
  • js 如何写构造函数 ,构造函数和普通函数有什么区别
  • MySQL-进阶篇-锁(全局锁、表级锁、行级锁)
  • c++懒汉式单例模式(Singleton)多种实现方式及最优比较
  • Gartner《2024中国安全技术成熟度曲线》AI安全助手代表性产品:开发者安全助手D10
  • 奇安信椒图--服务器安全管理系统(云锁)
  • pointer-events,添加水印的一个小小点
  • 微服务--认识微服务
  • 【docker】docker 镜像仓库的管理
  • 第L2周:机器学习-线性回归
  • SpringMVC拦截器深度解析与实战
  • 直线上最多的点数
  • 经济管理专业数据库介绍
  • 【C++ Primer Plus习题】11.1
  • [数据库][oracle]ORACLE EXP/IMP的使用详解
  • 中国各银行流动性比例数据(2000-2022年)
  • MACOS安装配置前端开发环境
  • Docker 配置国内镜像源
  • AI模块在人工智能中扮演着什么样的角色
  • VM Workstation虚拟机AlmaLinux 9.4操作系统安装(桌面版安装详细教程)(宝塔面板的安装),填补CentOS终止支持维护的空白
  • 【学习笔记】卫星通信NTN 3GPP标准化进展分析(三)- 3GPP Release17 内容