【图论】树上差分(边差分)
一.简介
其实点差分和边差分区别不大。
点差分中,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拷贝到运行文件夹下即可。...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
