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

352. 闇の連鎖(树上差分,LCA)

352. 闇の連鎖 - AcWing题库

传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物,古今中外的勇者们都试图打倒它。

经过研究,你发现 Dark 呈现无向图的结构,图中有 N 个节点和两类边,一类边被称为主要边,而另一类被称为附加边。

Dark 有 N–1 条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外,Dark 还有 M 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态,你只能选择一条主要边切断。

一旦你切断了一条主要边,Dark 就会进入防御模式,主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道,一共有多少种方案可以击败 Dark。

注意,就算你第一步切断主要边之后就已经把 Dark 斩为两截,你也需要切断一条附加边才算击败了 Dark。

输入格式

第一行包含两个整数 N 和 M。

之后 N–1 行,每行包括两个整数 A 和 B,表示 A 和 B 之间有一条主要边。

之后 M 行以同样的格式给出附加边。

输出格式

输出一个整数表示答案。

数据范围

N≤100000,M≤200000,数据保证答案不超过2^31−1

输入样例:
4 1
1 2
2 3
1 4
3 4
输出样例:
3

解析: 

”主要边“构成一棵树,”附加边“则是”非树边“。把一条附加边(x,y)添加到主要边构成的树中,会与树上 x,y 之间的路径形成一个环。如果第一步选择切断 x,y 之间路径上的某条边,那么第二步就必须切断附加边(x,y),才能令dark被斩为不连通的两部分。

因此,我们称每条附加边(x,y)都把树上 x,y 之间的路径上的每条边“覆盖了一次”。我们只需要统计出每条“主要边”被覆盖了多少次。若第一步把被覆盖0次的主要边切断,则第二步可以任意切断一条附加边。若第一次把覆盖1次的主要边切断,则第二步只能切断一条附加边。若第一次把覆盖2次及2次以上的主要边切断,则第二步怎么且都不能满足题意。据此我们可以统计出所有的方案数。

综上所述,下面我们要解决的问题模型是:给定一张无向图和一棵生成树,求每条“树边”被“非树边”覆盖了多少次。

解决此问题的经典做法就是“树上差分”。我们给树上每个节点一个初始为0的权值,然后对每条非树边(x,y),令节点 x 的权值加1,节点 y 的权值加1,节点 LCA(x,y)的权值减2。最后对这棵生成树进行一次深度优先遍历,求出 F[x] 表示以 x 为根的子树中各节点的权值之和。F[x] 就是 x 与它的父节点之间的“树边”被覆盖的次数。时间复杂度为 O(N+M)。

 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 2e5 + 5, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int depth[N],fa[N][17],d[N];
int q[N];
int ans;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void bfs() {int hh = 0, tt = 0;memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;q[tt++] = 1;while (hh != tt) {int t = q[hh++];if (hh == N)hh = 0;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q[tt++] = j;if (tt == N)tt = 0;fa[j][0] = t;for (int k = 1; k <= 16; k++) {fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}
}int lca(int a, int b) {if (depth[a] < depth[b])swap(a, b);for (int k = 16; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b])a = fa[a][k];}if (a == b)return a;for (int k = 16; k >= 0; k--) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}int dfs(int u,int father){int ret = d[u];for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j != father) {int s = dfs(j, u);if (!s)ans += m;else if (s == 1)ans++;ret += s;}}return ret;
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,a,b,c; i < n; i++) {scanf("%d%d", &a, &b);add(a, b), add(b, a);}bfs();for (int i = 1,a,b; i <= m; i++) {scanf("%d%d", &a, &b);int p = lca(a, b);d[a]++, d[b]++, d[p] -= 2;}dfs(1,-1);cout << ans << endl;return 0;
}

相关文章:

352. 闇の連鎖(树上差分,LCA)

352. 闇の連鎖 - AcWing题库 传说中的暗之连锁被人们称为 Dark。 Dark 是人类内心的黑暗的产物&#xff0c;古今中外的勇者们都试图打倒它。 经过研究&#xff0c;你发现 Dark 呈现无向图的结构&#xff0c;图中有 N 个节点和两类边&#xff0c;一类边被称为主要边&#xff…...

dcat admin + dingo + nginx 开发前台

前言 Dcat Admin 是一个功能强大的后端框架&#xff0c;主要用于开发管理后台。然而&#xff0c;大多数网站不仅需要一个管理后台&#xff0c;还需要一个用户界面&#xff0c;即“前台”&#xff0c;以及它们自己的用户系统。 为了实现这一目标&#xff0c;我们需要对 Dcat A…...

安卓线性布局LinearLayout

<?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:tools"http://schemas.android.com/tools"android:layout_width"match_parent"android:…...

Advanced CNN

文章目录 回顾Google NetInception1*1卷积Inception模块的实现网络构建完整代码 ResNet残差模块 Resedual Block残差网络的简单应用残差实现的代码 练习 回顾 这是一个简单的线性的卷积神经网络 然而有很多更为复杂的卷积神经网络。 Google Net Google Net 也叫Inception V…...

判断当前设备是不是安卓或者IOS?

代码(重要点): 当前文件要是 xxx.js文件,就需要写好代码后调用才会执行: // 判断是不是安卓 const isAndroid () > {return /android/.test(navigator.userAgent.toLowerCase()); }// 判断是不是ios const isIOS () > {return /iphone|ipad|ipod/.test(navigator.use…...

使用C++操作Matlab中的mat文件

matlab提供读写MAT文件的头文件和库函数&#xff0c;下面列出这些文件的路径&#xff0c;其中matlabroot指matlab安装的路径&#xff0c;arch来识别平台架构 头文件在matlabroot\extern\include库函数在matlabroot\bin\win64例程在matlabroot\extern\examples\eng_mat头文件 …...

【OCPP】ocpp1.6协议第3.5章节:本地授权和离线行为-介绍及翻译

目录 3.5章节 概述 3.5 本地鉴权和离线行为-译文(Local Authorization & Offline Behavior) 3.5.1 鉴权缓存-译文(3.5.1. Authorization Cache) 3.5.2 本地鉴权列表-译文(Local Authorization List) 3.5.3 授权缓存和本地授权列表之间的关系-译文(Relation between A…...

OpenGL查询对象 Query Objects

查询对象和异步查询(Query Objects and Asynchronous Queries) Query Objects&#xff08;查询对象&#xff09;是OpenGL中的一种机制&#xff0c;用于获取有关一系列GL命令处理过程的信息。这些信息可以包括&#xff1a; 绘图命令处理的图元数量。写入变换反馈缓冲区的图元数…...

【数据分享】1929-2023年全球站点的逐日最高气温数据(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、湿度等指标&#xff0c;其中又以气温指标最为常用&#xff01;说到气温数据&#xff0c;最详细的气温数据是具体到气象监测站点的气温数据&#xff01; 之前我们分享过1929-2023年全球气象站…...

Docker深入解析:从基础到实践

Docker基础知识 Docker是什么&#xff1a;定义和核心概念解释 Docker是一个开源项目&#xff0c;它诞生于2013年&#xff0c;旨在自动化应用程序的部署过程&#xff0c; 让应用程序能够在轻量级的、可移植的、自给自足的容器中运行。这些容器可以在几乎任何机器上运行&#xf…...

【鸿蒙】大模型对话应用(一):大模型接口对接与调试

Demo介绍 本demo对接阿里云和百度的大模型API&#xff0c;实现一个简单的对话应用。 DecEco Studio版本&#xff1a;DevEco Studio 3.1.1 Release HarmonyOS API版本&#xff1a;API9 关键点&#xff1a;ArkTS、ArkUI、UIAbility、网络http请求、列表布局 官方接口文档 此…...

SQL的函数类型

目录 一、聚合函数 二、数值型函数 三、字符串函数 四、日期函数 五、流程控制函数 一、聚合函数 定义&#xff1a;聚合函数是指对一组值进行运算&#xff0c;最终返回是单个值&#xff0c;也可以被称为组合函数。 COUNT() 统计目标行数量的函数 AVG() 求平均值 SU…...

TSINGSEE青犀视频智慧电梯管理平台,执行精准管理、提升乘梯安全

一、方案背景 随着城市化进程的不断加快&#xff0c;我国已经成为全球最大的电梯生产和消费市场&#xff0c;电梯也成为人们日常生活中不可或缺的一部分。随着电梯数量的激增&#xff0c;电梯老龄化&#xff0c;维保数据不透明&#xff0c;物业管理成本高&#xff0c;政府监管…...

VMware:在部分链上无法执行所调用的函数,请打开父虚拟磁

VMware:在部分链上无法执行所调用的函数&#xff0c;请打开父虚拟磁 问题&#xff1a;VMware给虚拟机扩展硬盘容量&#xff0c;提示&#xff1a;在部分链上无法执行所调用的函数&#xff0c;请打开父虚拟磁。原因&#xff1a;是因为你的虚拟磁盘文件是分多个文件存储的&#xf…...

【数据结构 08】红黑树

一、概述 红黑树&#xff0c;是一种二叉搜索树&#xff0c;每一个节点上有一个存储位表示节点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个节点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长上两倍&#xff0c;因而是接进…...

【百度Apollo】自动驾驶规划技术:实现安全高效的智能驾驶

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏:《linux深造日志》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! ⛳️ 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下…...

《C程序设计》上机实验报告(五)之一维数组二维数组与字符数组

实验内容&#xff1a; 1.运行程序 #include <stdio.h> void main( ) { int i,j,iRow0,iCol0,m; int x[3][4]{{1,11,22,33},{2,28,98,38},{3,85,20,89}}; mx[0][0]; for(i0;i<3;i) for(j0;j<4;j) if (x[i][j]>m) { mx[i][j]; iRowi…...

【BUG】联想Y7000电池电量为0且无法充电解决方案汇总

因为最近火灾很多&#xff0c;所以昨天夜晚睡觉的时候把插线板电源关掉了&#xff0c;电脑也关机了。 各位一定要注意用电安全&#xff0c;网上的那些事情看着真的很难受qvq。 第二天早上起床的时候一看发现电脑直接没电了&#xff0c;插上电源后也是显示 你一定要冲进去啊(ू˃…...

centos7常用命令之安装插件2

centos7安装插件1 7、kibana 【启动kibana,需要调整这个配置文件(/opt/kibana-6.3.0/config/kibana.yml)的一处ip地址,因为每次虚拟机的ip地址可能会有所不同&#xff0c; 同时访问页面地址的ip:5601时,ip地址也对应修改】 1.解压缩包 cd /opt/ tar -xvf kibana-6.3.0-linux-x…...

MATLAB - 仿真单摆的周期性摆动

系列文章目录 前言 本例演示如何使用 Symbolic Math Toolbox™ 模拟单摆的运动。推导摆的运动方程&#xff0c;然后对小角度进行分析求解&#xff0c;对任意角度进行数值求解。 一、步骤 1&#xff1a;推导运动方程 摆是一个遵循微分方程的简单机械系统。摆最初静止在垂直位置…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...