AcWing1171. 距离(lcatarjan)

输入样例1:
2 2
1 2 100
1 2
2 1
输出样例1:
100
100
输入样例2:
3 2
1 2 10
3 1 15
1 2
3 2
输出样例2:
10
25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,x,y,k,res[N];
int vis[N];
int dis[N];
int p[N];
vector<pair<int,int>>query[N],e[N];void dfs(int u,int fa){for(auto it:e[u]){int to=it.first;if(to==fa) continue;dis[to]=dis[u]+it.second;dfs(to,u);}
}
int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
void tarjan(int u){vis[u]=1;for(auto it:e[u]){int to=it.first;if(!vis[to]){tarjan(to);p[to]=u;}}for(auto it:query[u]){int y=it.first;int id=it.second;if(vis[y]==2){int anc=find(y);res[id]=dis[u]+dis[y]-dis[anc]*2;}}vis[u]=2;
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<n-1;i++){scanf("%d%d%d",&x,&y,&k);e[x].push_back({y,k});e[y].push_back({x,k});}for(int i=0;i<m;i++){scanf("%d%d",&x,&y);if(x!=y){query[x].push_back({y,i});query[y].push_back({x,i});}}for(int i=1;i<=n;i++) p[i]=i;dfs(1,-1);tarjan(1);for(int i=0;i<m;i++) printf("%d\n",res[i]);return 0;
}
相关文章:
AcWing1171. 距离(lcatarjan)
输入样例1: 2 2 1 2 100 1 2 2 1输出样例1: 100 100输入样例2: 3 2 1 2 10 3 1 15 1 2 3 2输出样例2: 10 25 #include<bits/stdc.h> using namespace std; typedef long long ll; const int N2e55; int n,m,x,y,k,r…...
JVM-运行时数据区
目录 什么是运行时数据区? 方法区 堆 程序计数器 虚拟机栈 局部变量表 操作数栈 动态连接 运行时常量池 方法返回地址 附加信息 本地方法栈 总结: 什么是运行时数据区? Java虚拟机在执行Java程序时,将它管…...
RedisTemplate中boundHashOps的使用
1、往指定key中存储 键值 redisTemplate.boundHashOps("demo").put("1",1); 2、根据指定key中得键取出值 System.out.println(redisTemplate.boundHashOps("demo").get("1")); 3、根据指定key中得键删除 redisTemplate.boundHash…...
计算机网络-性能指标
计算机网络-性能指标 文章目录 计算机网络-性能指标简介速率比特速率 带宽吞吐量时延时延计算 时延带宽积往返时间网络利用率丢包率总结 简介 性能指标可以从不同的方面来度量计算机网络的性能 常用的计算机网络的性能指标有以下8个 速率带宽吞吐量时延时延带宽积往返时间利…...
排序第一课【插入排序】直接插入排序 与 希尔排序
目录 1. 排序的概念: 2.插入排序基本思想 3.直接插入排序 4.希尔排序 1. 排序的概念: 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性…...
云计算——ACA学习 云计算概述
作者简介:一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 目录 写在前面 上章回顾 本章简介 本章目标 一.云计算产生背景 1.信息时代的重点变革…...
如何为网站进行全面的整站翻译?
要翻译整个网站,可以按照以下步骤进行: 确定翻译需求:确定你需要将整个网站翻译成哪种语言。这可以根据你的目标受众和市场进行决定。 寻找翻译资源:你可以选择以下几种方式来进行网站翻译: a. 人工翻译:雇…...
项目部署(前后端分离)
1、前端项目 (打包成dist文件,放到nginx的html目录下面),然后配置nginx 2、后端项目部署 使用之前的shell脚本(然后赋予用户权限),最后运行脚本 查看进程...
增强型Web安全网关在银行的应用
销售,绝不是降低身份去取悦客户,而是像朋友一样给予合理的建议。你刚好需要,我刚好专业!仅此而已! 乔.吉拉德 健康的安全体系,还可以更完善 浙江某商业银行股份有限公司是一家成立多年的商业银行…...
Oracle-ORA-00600:[ktspffbmb:objdchk_kcbnew_3]
问题背景: 应用执行存储过程报错ORA-00600: 内部错误代码, 参数: [ktspffbmb:objdchk_kcbnew_3], [0], [3303775], [4], [], [], [], [], [], [], [], [],导致过程无法正常执行 ORA-00600: 内部错误代码, 参数: [ktspffbmb:objdchk_kcbnew_3], [0], [3303775], [4]…...
SPINN:基于设备和云的神经网络协同递进推理
SPINN:基于设备和云的神经网络协同递进推理 论文标题:SPINN: synergistic progressive inference of neural networks over device and cloud 原文链接:https://dl.acm.org/doi/10.1145/3372224.3419194 论文动机 现代CNN过多的计算需求&am…...
数据结构-二叉树
数据结构-二叉树 二叉树的概念二叉树的遍历分类 建立二叉树,并遍历二叉树的最小单元二叉树的最小单元初始化初始化二叉树前序遍历的实现中序遍历的实现后序遍历的实现计算节点的个数计算树的深度求第k层的个数查找二叉树的元素分层遍历 全部代码如下 二叉树的概念 二…...
Open3D 进阶(4)高斯混合点云聚类
目录 一、算法原理1、原理概述2、实现流程3、参考文献二、代码实现三、结果展示四、测试数据本文由CSDN点云侠原创,原文链接。爬虫网站自重。 一、算法原理 1、原理概述 高斯混合聚类(GMM)算法假设数据点是由一个或多个高斯分布生成的,并通过最大似然估计的方法来估计每个簇…...
计算机组成和IO
文章目录 计组和Epoll:计算机组成原理:网络数据接收的流程:内核如何管理socket以及状态的更新select系统调用的复杂度epoll的et和lt模式及java的选择 国内访问chatai就可以 https://aiweb.douguguo.com/?typeadd计组和Epoll: 计…...
STM32CUBUMX配置RS485 modbus STM32(从机)亲测可用
———————————————————————————————————— ⏩ 大家好哇!我是小光,嵌入式爱好者,一个想要成为系统架构师的大三学生。 ⏩最近在开发一个STM32H723ZGT6的板子,使用STM32CUBEMX做了很多驱动&#x…...
系统设计类题目汇总
1 设计一个系统统计当前时刻北京用户在线人数 【Redis】位图以及位图的使用场景(统计在线人数和用户在线状态) 1.1 方案一: 在用户登录时,使用 Redis SET 将用户 ID 添加到一个特定的键(例如 “online:beijing”)。用户退出时&…...
css滚动条样式指南
css滚动条样式指南 滚动条是网页设计中经常被忽视的元素。虽然它看起来像是一个小细节,但它在网站导航中起着至关重要的作用。默认的滚动条可能看起来不合适,有损整体美观。本文将介绍如何使用 CSS 自定义滚动条。 在 Chrome、Edge 和 Safari 中设置滚…...
vue子组件修改父组件传递的变量(自定义日期时间组件,时间间隔为15分钟或者一个小时)
vue子组件修改父组件传递的变量 子组件不能直接修改父组件变量的值,但是可以通过调用父组件的方法来修改。 实现步骤 在父组件声明变量 export default {data() {return {startTime:"",......},......} }在父组件使用子组件并传递数据,修改…...
【PyTorch】nn.Conv2d函数详解
nn.Conv2d 是 PyTorch 中的一个卷积层,用于实现二维卷积操作 torch.nn.Conv2d(in_channels, out_channels, kernel_size, stride1, padding0, dilation1, groups1, biasTrue, padding_modezeros, deviceNone, dtypeNone )参数解释 in_channels:输入的通…...
数智保险 创新未来 | GBASE南大通用亮相中国保险科技应用高峰论坛
本届峰会以“数智保险 创新未来”为主题,GBASE南大通用携新一代创新数据库产品及金融信创解决方案精彩亮相,与国内八百多位保险公司高管和众多保险科技公司技术专家,就保险领域数字化的创新应用及生态建设、新一代技术突破及发展机遇、前沿科…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
