当前位置: 首页 > news >正文

【图论】树上差分(边差分)

一.简介

其实点差分和边差分区别不大。

点差分中,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;
}

相关文章:

【图论】树上差分(边差分)

一.简介 其实点差分和边差分区别不大。 点差分中&#xff0c;d数组存储的是树上的节点 边差分中&#xff0c;d数组存储的是当前节点到父节点的那条边的差分值。 指定注意的是&#xff1a;边差分中因为根连的父节点是虚点&#xff0c;所以遍历结果时应当忽略&#xff01; 二…...

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.样本准备 收集好你所需的正样本&#xff0c;和负样本&#xff0c;分别保存在不同文件夹 在pycharm新建项目&#xff0c;项目结构如下&#xff1a;has_mask文件夹放置正样本&#xff0c;no_mask文件夹放置负样本 安装opencv&#xff0c;把opencv包…...

详解Mybatis之分页插件【PageHelper】

编译软件&#xff1a;IntelliJ IDEA 2019.2.4 x64 操作系统&#xff1a;win10 x64 位 家庭版 Maven版本&#xff1a;apache-maven-3.6.3 Mybatis版本&#xff1a;3.5.6 文章目录 一. 什么是分页&#xff1f;二. 为什么使用分页&#xff1f;三. 如何设计一个Page类&#xff08;分…...

【基于矢量射线的衍射积分 (VRBDI)】基于矢量射线的衍射积分 (VRBDI) 和仿真工具(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

基于jackson对bean的序列号和反序列化

通过观察控制台输出的SQL发现页面传递过来的员工id的值和数据库中的id值不一致&#xff0c;这是怎么回事呢? 分页查询时服务端响应给页面的数据中id的值为19位数字&#xff0c;类型为long 页面中js处理long型数字只能精确到前16位&#xff0c;所以最终通过ajax请求提交给服务…...

排队理论简介

排队理论简介 1. 理论背景2. 研究的数学方法3. 拒绝型排队系统与等候型排队系统4. 拒绝型排队系统 本文参考文献为Вентцель Е. С.的《Исследование операций》。 1. 理论背景 排队理论又称大众服务理论&#xff0c;顾名思义指的是在有限的服务条…...

极速查找(3)-算法分析

篇前小言 本篇文章是对查找&#xff08;2&#xff09;的续讲二叉排序树 二叉排序树&#xff08;Binary Search Tree&#xff0c;BST&#xff09;&#xff0c;又称为二叉查找树&#xff0c;是一种特殊的二叉树。性质&#xff1a; 左子树的节点值小于根节点的值&#xff0c;右…...

http 常见的响应状态码 ?

100——客户必须继续发出请求101——客户要求服务器根据请求转换HTTP协议版本200——交易成功201——提示知道新文件的URL202——接受和处理、但处理未完成203——返回信息不确定或不完整204——请求收到&#xff0c;但返回信息为空205——服务器完成了请求&#xff0c;用户代理…...

机器学习笔记之优化算法(四)线搜索方法(步长角度;非精确搜索)

机器学习笔记之优化算法——线搜索方法[步长角度&#xff0c;非精确搜索] 引言回顾&#xff1a;精确搜索步长及其弊端非精确搜索近似求解最优步长的条件反例论述 引言 上一节介绍了从精确搜索的步长角度观察了线搜索方法&#xff0c;本节将从非精确搜索的步长角度重新观察线搜…...

Redis 哨兵 (sentinel)

是什么 官网理论&#xff1a;https://redis.io/docs/management/sentinel/ 吹哨人巡查监控后台 master 主机是否故障&#xff0c;如果故障了根据投票数自动将某一个从库转换为新主库&#xff0c;继续对外服务。 作用&#xff1a;无人值守运维 哨兵的作用&#xff1a; 1…...

统计2021年10月每个退货率不大于0.5的商品各项指标

统计2021年10月每个退货率不大于0.5的商品各项指标_牛客题霸_牛客网s mysql&#xff08;ifnull&#xff09;&#xff1a; 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代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

UE5、CesiumForUnreal加载无高度地形

文章目录 1.实现目标2.实现过程3.参考资料1.实现目标 在UE5中,CesiumForUnreal插件默认的地形都是带高度的,这里加载没有高度的地形,即大地高程为0,GIF动图如下: 2.实现过程 参考官方的教程,下载无高度的DEM,再切片加载到UE中。 (1)下载无高度地形DEM0。 在官方帖子…...

关于Spring中的@Configuration中的proxyBeanMethods属性

Configuration的proxyBeanMethods属性 在Configuration注解中&#xff0c;有两个属性&#xff1a; value配置Bean名称proxyBeanMethos&#xff0c;默认是true 这个proxyBeanMethods的默认属性是true。 直接说&#xff1a;当Configuration注解的proxyBeanMeathods属性是true…...

dp1,ACM暑期培训

D - 摆花 P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Description 小明的花店新开张&#xff0c;为了吸引顾客&#xff0c;他想在花店的门口摆上一排花&#xff0c;共 m 盆。通过调查顾客的喜好&#xff0c;小明列出了顾客最喜欢的 n 种花&…...

大厂程序员的水平比非大厂高很多嘛?

最近一个月&#xff0c;筛选了一百多份简历&#xff0c;前前后后面试了二三十人&#xff0c;基本上都是有大厂经历的人。同时&#xff0c;也录用了几个有大厂经历的。但整体而言&#xff0c;打破了对大厂出来的都是优质人才的幻觉。看到的实际情况与想象中的落差还是比较大的。…...

Java开发工具MyEclipse发布v2023.1.2,今年第二个修复版!

MyEclipse一次性提供了巨量的Eclipse插件库&#xff0c;无需学习任何新的开发语言和工具&#xff0c;便可在一体化的IDE下进行Java EE、Web和PhoneGap移动应用的开发&#xff1b;强大的智能代码补齐功能&#xff0c;让企业开发化繁为简。 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.运行完毕后&#xff0c;双击打开exe文件&#xff0c;可能会报错&#xff0c;缺少相关的dll,找到缺少的dll拷贝到运行文件夹下即可。...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...