【图论】树上差分(边差分)
一.简介
其实点差分和边差分区别不大。
点差分中,d数组存储的是树上的节点
边差分中,d数组存储的是当前节点到父节点的那条边的差分值。
指定注意的是:边差分中因为根连的父节点是虚点,所以遍历结果时应当忽略!

二.题目

样例输入:
4 1
1 2
2 3
1 4
3 4样例输出:3
三.题目分析
我们易知:
加上一条边时,相当于把所经过的节点都加了一条命。(这时用差分快一些)
(为了方便,我们令边的权值为-1时,才算断掉)
若一条边最后还是没加命,即0;所以切断它,图就不连通了,所以红边任意切一条即可。所以此边贡献为m;
若这条边有一条命,我们切断它后,它还有一条命,固只能再切掉给它续命的那条红边,图才不联通,所以此边贡献为1;
若这条边有2条以及以上条命,我们显然要切3次及三次以上。但我们只能切二次。它命太硬了,所以我们放弃这条边。次边贡献为0;
四.参考代码
/*
4 1
1 2
2 3
1 4
3 4
*/#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
struct Edge{int u,v,next;
}edge[maxn<<1];
int head[maxn],cnt=0;
void add(int u,int v){edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
int depth[maxn],p[maxn][30],d[maxn];
void dfs1(int u,int fa){depth[u]=depth[fa]+1;p[u][0]=fa;for(int i=1;(1<<i)<=depth[u];i++){p[u][i]=p[p[u][i-1]][i-1];}for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(fa!=v) dfs1(v,u);}
}
int LCA(int x,int y){if(depth[x]<depth[y]) swap(x,y);int lg=0;while((1<<lg)<=depth[x]) lg++;for(int i=lg;i>=0;i--){if(depth[x]-(1<<i)>=depth[y]){x=p[x][i];}}if(x==y) return x;for(int i=lg;i>=0;i--){if(p[x][i]!=p[y][i]){x=p[x][i]; y=p[y][i];}}return p[x][0];
}
void dfs2(int u,int fa){for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs2(v,u);d[u]+=d[v];}}
}
int main(){//读入数据 scanf("%d%d",&n,&m);int u,v;for(int i=1;i<n;i++){scanf("%d%d",&u,&v);add(u,v); add(v,u);}//建树 dfs1(1,0);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);d[u]++; d[v]++;int lca=LCA(u,v);d[lca]-=2;}//sum原数组dfs2(1,0); int ans=0;//i从2开始,因为1连的父节点是虚点 for(int i=2;i<=n;i++){if(d[i]==0) ans+=m;else if(d[i]==1) ans++;}cout<<ans;return 0;
}
相关文章:
【图论】树上差分(边差分)
一.简介 其实点差分和边差分区别不大。 点差分中,d数组存储的是树上的节点 边差分中,d数组存储的是当前节点到父节点的那条边的差分值。 指定注意的是:边差分中因为根连的父节点是虚点,所以遍历结果时应当忽略! 二…...
RT1052的定时器
文章目录 1 通用定时器1.1 定时器框图1.2 实现周期性中断 2 相关寄存器3 定时器配置3.1 时钟使能3.2 初始化GPT1定时器3.2.1 base3.2.2 initConfig3.2.2.1 clockSorce3.2.2.2 divider3.2.2.3 enablexxxxx 3.3 设置 GPT1 比较值3.3.1 base3.3.2 channel3.3.3 value 3.4 设置 GPT…...
opencv python 训练自己的分类器
源码下载 一、分类器制作 1.样本准备 收集好你所需的正样本,和负样本,分别保存在不同文件夹 在pycharm新建项目,项目结构如下:has_mask文件夹放置正样本,no_mask文件夹放置负样本 安装opencv,把opencv包…...
详解Mybatis之分页插件【PageHelper】
编译软件:IntelliJ IDEA 2019.2.4 x64 操作系统:win10 x64 位 家庭版 Maven版本:apache-maven-3.6.3 Mybatis版本:3.5.6 文章目录 一. 什么是分页?二. 为什么使用分页?三. 如何设计一个Page类(分…...
【基于矢量射线的衍射积分 (VRBDI)】基于矢量射线的衍射积分 (VRBDI) 和仿真工具(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
基于jackson对bean的序列号和反序列化
通过观察控制台输出的SQL发现页面传递过来的员工id的值和数据库中的id值不一致,这是怎么回事呢? 分页查询时服务端响应给页面的数据中id的值为19位数字,类型为long 页面中js处理long型数字只能精确到前16位,所以最终通过ajax请求提交给服务…...
排队理论简介
排队理论简介 1. 理论背景2. 研究的数学方法3. 拒绝型排队系统与等候型排队系统4. 拒绝型排队系统 本文参考文献为Вентцель Е. С.的《Исследование операций》。 1. 理论背景 排队理论又称大众服务理论,顾名思义指的是在有限的服务条…...
极速查找(3)-算法分析
篇前小言 本篇文章是对查找(2)的续讲二叉排序树 二叉排序树(Binary Search Tree,BST),又称为二叉查找树,是一种特殊的二叉树。性质: 左子树的节点值小于根节点的值,右…...
http 常见的响应状态码 ?
100——客户必须继续发出请求101——客户要求服务器根据请求转换HTTP协议版本200——交易成功201——提示知道新文件的URL202——接受和处理、但处理未完成203——返回信息不确定或不完整204——请求收到,但返回信息为空205——服务器完成了请求,用户代理…...
机器学习笔记之优化算法(四)线搜索方法(步长角度;非精确搜索)
机器学习笔记之优化算法——线搜索方法[步长角度,非精确搜索] 引言回顾:精确搜索步长及其弊端非精确搜索近似求解最优步长的条件反例论述 引言 上一节介绍了从精确搜索的步长角度观察了线搜索方法,本节将从非精确搜索的步长角度重新观察线搜…...
Redis 哨兵 (sentinel)
是什么 官网理论:https://redis.io/docs/management/sentinel/ 吹哨人巡查监控后台 master 主机是否故障,如果故障了根据投票数自动将某一个从库转换为新主库,继续对外服务。 作用:无人值守运维 哨兵的作用: 1…...
统计2021年10月每个退货率不大于0.5的商品各项指标
统计2021年10月每个退货率不大于0.5的商品各项指标_牛客题霸_牛客网s mysql(ifnull): select product_id, format(ifnull(sum(if_click)/nullif(count(*),0),0),3) as ctr, format(ifnull(sum(if_cart)/nullif(sum(if_click),0),0),3) as c…...
【小波尺度谱】从分段离散小波变换计算小波尺度谱研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
UE5、CesiumForUnreal加载无高度地形
文章目录 1.实现目标2.实现过程3.参考资料1.实现目标 在UE5中,CesiumForUnreal插件默认的地形都是带高度的,这里加载没有高度的地形,即大地高程为0,GIF动图如下: 2.实现过程 参考官方的教程,下载无高度的DEM,再切片加载到UE中。 (1)下载无高度地形DEM0。 在官方帖子…...
关于Spring中的@Configuration中的proxyBeanMethods属性
Configuration的proxyBeanMethods属性 在Configuration注解中,有两个属性: value配置Bean名称proxyBeanMethos,默认是true 这个proxyBeanMethods的默认属性是true。 直接说:当Configuration注解的proxyBeanMeathods属性是true…...
dp1,ACM暑期培训
D - 摆花 P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Description 小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n 种花&…...
大厂程序员的水平比非大厂高很多嘛?
最近一个月,筛选了一百多份简历,前前后后面试了二三十人,基本上都是有大厂经历的人。同时,也录用了几个有大厂经历的。但整体而言,打破了对大厂出来的都是优质人才的幻觉。看到的实际情况与想象中的落差还是比较大的。…...
Java开发工具MyEclipse发布v2023.1.2,今年第二个修复版!
MyEclipse一次性提供了巨量的Eclipse插件库,无需学习任何新的开发语言和工具,便可在一体化的IDE下进行Java EE、Web和PhoneGap移动应用的开发;强大的智能代码补齐功能,让企业开发化繁为简。 MyEclipse v2023.1.2官方正式版下载 …...
基于正交滤波器组的语音DPCM编解码算法matlab仿真
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 ...........................................................g0zeros(1,lenH); g1zeros(1,l…...
VS2022和QT混合编程打包发布程序
1.在开始菜单输入 CMD 找到 Qt5.15.2(MSVC 64-bit) 2.输入windeployqt exe所在路径 3.运行完毕后,双击打开exe文件,可能会报错,缺少相关的dll,找到缺少的dll拷贝到运行文件夹下即可。...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)
Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...
