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南大通用携新一代创新数据库产品及金融信创解决方案精彩亮相,与国内八百多位保险公司高管和众多保险科技公司技术专家,就保险领域数字化的创新应用及生态建设、新一代技术突破及发展机遇、前沿科…...
3步让PS手柄在Windows上完美运行:DS4Windows终极配置指南
3步让PS手柄在Windows上完美运行:DS4Windows终极配置指南 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows 你是否曾为心爱的PlayStation手柄在Windows电脑上无法被游戏识别而烦…...
如何永久免费使用IDM:开源激活脚本完整使用指南
如何永久免费使用IDM:开源激活脚本完整使用指南 【免费下载链接】IDM-Activation-Script IDM Activation & Trail Reset Script 项目地址: https://gitcode.com/gh_mirrors/id/IDM-Activation-Script 你是否厌倦了Internet Download Manager(…...
CANN/asc-devkit atanf函数文档
atanf 【免费下载链接】asc-devkit 本项目是CANN 推出的昇腾AI处理器专用的算子程序开发语言,原生支持C和C标准规范,主要由类库和语言扩展层构成,提供多层级API,满足多维场景算子开发诉求。 项目地址: https://gitcode.com/cann…...
RAG:终结AI幻觉,让你的大语言模型秒变“知识渊博”!
本文深入浅出地介绍了检索增强生成(RAG)技术,解释了其如何通过结合文档检索与大语言模型(LLM),有效减少AI幻觉现象。文章详细阐述了RAG的工作流程,包括数据分块、嵌入转换、向量数据库存储、问题…...
AI智能体驱动的海上风电制氢模型:技术解析与经济性评估
## 引言:当AI遇上海上风电制氢 在全球碳中和目标的推动下,海上风电制氢技术正从概念走向工程实践。然而,风电的间歇性与电解槽的响应特性之间的矛盾,一直是制约系统效率的瓶颈。近年来,AI智能体的引入为这一难题提供了…...
零经验应届生简历怎么写?3分钟AI生成直接拿面试
毕业季到了,你是不是也跟我一样,简历投了几十份,结果石沉大海,连个面试机会都没有?尤其看到那些社招大佬,简历上项目经验、数据成果写得一套一套的,再看看自己的,除了实习经历就是课…...
这份榜单够用!盘点2026年断层领先的的AI论文写作软件
一天写完毕业论文在2026年已不再是天方夜谭。以下是2026年最炸裂、实测能大幅提速的AI论文写作软件,覆盖选题构思、文献综述、数据整理、格式排版等核心场景,帮你高效搞定论文。 一、全流程王者:一站式搞定论文全链路(一天定稿首选…...
2026年论文党必备:降AI率平台测评与推荐指南
2026年真正好用的AI论文降重与改写工具,核心看降重效果、去AI味、格式保留、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 …...
书匠策AI降重降AIGC到底有多野?论文党看完直接封神!
各位论文战士们,今天不聊开题,不聊答辩,咱们聊点真正救命的东西——降重和降AIGC。 你有没有经历过这种绝望:查重报告一出来,红得像过年的对联?导师一句"你这AIGC率太高了,重写"&…...
阅读APP书源导入与使用完全指南:26个高质量书源一键获取
阅读APP书源导入与使用完全指南:26个高质量书源一键获取 【免费下载链接】Yuedu 📚「阅读」自用书源分享 项目地址: https://gitcode.com/gh_mirrors/yu/Yuedu 还在为「阅读」APP找不到稳定的小说书源而烦恼吗?这款开源阅读工具需要自…...
