【图论】虚树 - 模板总结
适用于解决一棵树中只需要用到少部分点的时候,将需要用到的点提出来单独建一棵树
/********************* 虚树 *********************/
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同学啊 目标: 学习简单线性回归模型和多元线性回归模型通过代码实现:通过鸢尾花花瓣长度预测花瓣宽度 具体实现: (一&…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
负载均衡器》》LVS、Nginx、HAproxy 区别
虚拟主机 先4,后7...
DeepSeek越强,Kimi越慌?
被DeepSeek吊打的Kimi,还有多少人在用? 去年,月之暗面创始人杨植麟别提有多风光了。90后清华学霸,国产大模型六小虎之一,手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水,单月光是投流就花费2个亿。 疯…...
SQL注入篇-sqlmap的配置和使用
在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap,但是由于很多朋友看不了解命令行格式,所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习,链接:https://wwhc.lanzoue.com/ifJY32ybh6vc…...
Linux入门课的思维导图
耗时两周,终于把慕课网上的Linux的基础入门课实操、总结完了! 第一次以Blog的形式做学习记录,过程很有意思,但也很耗时。 课程时长5h,涉及到很多专有名词,要去逐个查找,以前接触过的概念因为时…...
自定义线程池1.2
自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本,将线程池中的线程数量交给使用者决定,并且将线程的创建延迟到任务提交的时候,在本文中我们将对这个版本进行如下的优化: 在新建线程时交给线程一个任务。让线程在某种情况下…...
使用 uv 工具快速部署并管理 vLLM 推理环境
uv:现代 Python 项目管理的高效助手 uv:Rust 驱动的 Python 包管理新时代 在部署大语言模型(LLM)推理服务时,vLLM 是一个备受关注的方案,具备高吞吐、低延迟和对 OpenAI API 的良好兼容性。为了提高部署效…...
