当前位置: 首页 > 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;推导运动方程 摆是一个遵循微分方程的简单机械系统。摆最初静止在垂直位置…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...