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

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...