【图论】虚树 - 模板总结
适用于解决一棵树中只需要用到少部分点的时候,将需要用到的点提出来单独建一棵树
/********************* 虚树 *********************/
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同学啊 目标: 学习简单线性回归模型和多元线性回归模型通过代码实现:通过鸢尾花花瓣长度预测花瓣宽度 具体实现: (一&…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
