【图论】虚树 - 模板总结
适用于解决一棵树中只需要用到少部分点的时候,将需要用到的点提出来单独建一棵树
/********************* 虚树 *********************/
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;
/***********************************************/
相关文章:
【图论】虚树 - 模板总结
适用于解决一棵树中只需要用到少部分点的时候,将需要用到的点提出来单独建一棵树 /********************* 虚树 *********************/ struct edge {int to, next;int val; };struct Virtual_Tree {int n; // 点数int dfn[N]; // dfs序int dep[N]; // 深度int fa…...
[C#学习笔记]注释
官方文档:Documentation comments - C# language specification | Microsoft Learn 一、常用标记总结 1.1 将文本设置为代码风格的字体:<c> 1.2 源代码或程序输出:<code> 1.3 异常指示:<exception> 1.4 段落 <para> 1.5 换行&…...
c# checkbox的text文字放到右边
checkbox的text文字放到右边 实现方法如下图 特此记录 anlog 2024年9月2日...
【node.js】基础之修改文件
node.js 基础(一) node.js是什么? 上面这句话的意思就是:Node.js 是一个开源的,跨平台的javascript运行环境。通俗的说就是一个应用程序或者说是一个软件,可以运行javascript。 Node.js的作用: 开发服务器应用。 将数…...
Notepad++回车不自动补全
问题 使用Notepad时,按回车经常自动补全,但我们希望回车进行换行,而不是自动补全,而且自动补全使用Tab进行补全足够了。下文介绍设置方法。 设置方法 打开Notepad,进入设置 - 首选项 - 自动完成,在插入选…...
CSS线性渐变拼接,一个完整的渐变容器(div),要拆分成多个渐变容器(div),并且保持渐变效果一致
1 需求 一个有渐变背景的div,需要替换成多个渐变背景div拼接,渐变效果需要保持一致(不通过一个大的div渐变,其他子的div绝对定位其上并且背景透明来解决) 2 分析 主要工作: 计算完整div背景线性渐变时的…...
【60天备战软考高级系统架构设计师——第十天:软件设计与架构综合练习】
经过前十天的学习,我们已经了解了软件工程生命周期模型、需求分析与管理方法,以及软件设计与架构的核心内容。为了巩固这些知识点,今天我们将进行一个综合练习。 前十天学习内容回顾 第1-3天:软件工程概述 学习了软件生命周期模…...
2024.8.15(python管理mysql、Mycat实现读写分离)
一、python管理mysql 1、搭建主mysql [rootmysql57 ~]# tar -xf mysql-5.7.44-linux-glibc2.12-x86_64.tar.gz [rootmysql57 ~]# cp -r mysql-5.7.44-linux-glibc2.12-x86_64 /usr/local/mysql [rootmysql57 ~]# rm -rf /etc/my.cnf [rootmysql57 ~]# mkdir /usr/local/mysql…...
CMU 10423 Generative AI:lec2
文章目录 1 概述2 部分摘录2.1 噪声信道模型(Noisy Channel Models)主要内容:公式解释:应用举例: 2.2 n-Gram模型1. 什么是n-Gram模型2. 早期的n-Gram模型3. Google n-Gram项目4. 模型规模与训练数据5. n-Gram模型的局…...
恋爱相亲交友系统源码原生源码可二次开发APP 小程序 H5,web全适配
直播互动:平台设有专门的直播间,允许房间主人与其他异性用户通过视频连线的方式进行一对一互动。语音视频交流:异性用户可以发起语音或视频通话,以增进了解和交流。群组聊天:用户能够创建群聊,邀请自己关注…...
OceanBase 4.x 存储引擎解析:如何让历史库场景成本降低50%+
据国际数据公司(IDC)的报告显示,预计到2025年,全球范围内每天将产生高达180ZB的庞大数据量,这一趋势预示着企业将面临着更加严峻的海量数据处理挑战。随着数据日渐庞大,一些存储系统会出现诸如存储空间扩展…...
js 如何写构造函数 ,构造函数和普通函数有什么区别
在 JavaScript 中,构造函数是一种特殊的函数,用于初始化一个新创建的对象。构造函数通常用来创建具有相似属性和方法的对象实例。构造函数的主要特点是在调用时使用 new 关键字,这样就会创建一个新对象,并将其原型设置为构造函数的…...
MySQL-进阶篇-锁(全局锁、表级锁、行级锁)
文章目录 1. 锁概述2. 全局锁2.1 介绍2.2 数据备份2.3 使用全局锁造成的问题 3. 表级锁3.1 表锁3.1.1 语法3.1.2 读锁3.1.3 写锁3.1.4 读锁和写锁的区别 3.2 元数据锁(Meta Data Lock,MDL)3.3 意向锁3.3.1 案例引入3.3.2 意向锁的分类 4. 行级…...
c++懒汉式单例模式(Singleton)多种实现方式及最优比较
前言 关于C懒汉式单例模式的写法,大家都很熟悉。早期的设计模式中有代码示例。比如: class Singleton {private: static Singleton *instance;public: static Singleton *getInstance() {if (NULL instance)instance new Singleton();return instanc…...
Gartner《2024中国安全技术成熟度曲线》AI安全助手代表性产品:开发者安全助手D10
海云安关注到,近日,国际权威研究机构Gartner发布了《2024中国安全技术成熟度曲线》(Hype Cycle for Security in China,2024)报告。 在此次报告中,安全技术成熟度曲线将安全周期划分为技术萌芽期(Innovation Trigger)…...
奇安信椒图--服务器安全管理系统(云锁)
奇安信椒图–服务器安全管理系统(云锁) 椒图 奇安信服务器安全管理系统是一款符合Gartner定义的CWPP(云工作负载保护平台)标准、EDR(终端检测与响应)、EPP终端保护平台(终端保护平台ÿ…...
pointer-events,添加水印的一个小小点
场景:平平无奇一个水印图,这类功能实现:就是覆盖在整个可视div后,又加了一个div(使用定位canvas画一个水印图充当背景),可时我好奇的是,我使用控制台,选择对应的元素时&a…...
微服务--认识微服务
微服务架构的演变 1. 单体架构(Monolithic) 阶段描述:在单体应用时代,整个应用程序被设计为一个项目,并在一个进程内运行。这种架构方式开发简单,便于集中管理,但随着应用的复杂化,…...
【docker】docker 镜像仓库的管理
Docker 仓库( Docker Registry ) 是用于存储和分发 Docker 镜像的集中式存储库。 它就像是一个大型的镜像仓库,开发者可以将自己创建的 Docker 镜像推送到仓库中,也可以从仓库中拉取所需的镜像。 Docker 仓库可以分为公共仓…...
第L2周:机器学习-线性回归
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 目标: 学习简单线性回归模型和多元线性回归模型通过代码实现:通过鸢尾花花瓣长度预测花瓣宽度 具体实现: (一&…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
