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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79496.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

算法通关村—轻松搞定二叉树的高度和深度问题

1.二叉树的最大深度 二叉树的最大深度 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 1.1 递归 通过上面的步骤能够看出&#xff0c;深度取决于左右子树&#xff0c;只要左子树有&#xff0c;那么高…

gateway过滤器没生效,特殊原因

看这边文章的前提&#xff0c;你要会gateway&#xff0c;知道过滤器怎么配置&#xff1f; 直接来看过滤器&#xff0c;局部过滤器 再来看配置 请求路径 http://127.0.0.1:8080/appframework/services/catalog/catalogSpecials.json?pageindex1&pagesize10&pkidd98…

php-cgi.exe - FastCGI 进程超过了配置的请求超时时限

解决方案一&#xff1a; 处理(php-cgi.exe - FastCGI 进程超过了配置的请求超时时限)的问题 内容转载&#xff1a; 处理(php-cgi.exe - FastCGI 进程超过了配置的请求超时时限)的问题_php技巧_脚本之家 【详细错误】&#xff1a; HTTP 错误 500.0 - Internal Server Error C:…

go编译文件

1.编译go文件 go build [go文件]2.执行文件编译文件 ./demo [demo为go文件名称]

2023-08-06 LeetCode每日一题(24. 两两交换链表中的节点)

2023-08-06每日一题 一、题目编号 24. 两两交换链表中的节点二、题目链接 点击跳转到题目位置 三、题目描述 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0…

Kubernetes高可用集群二进制部署(四)部署kubectl和kube-controller-manager、kube-scheduler

Kubernetes概述 使用kubeadm快速部署一个k8s集群 Kubernetes高可用集群二进制部署&#xff08;一&#xff09;主机准备和负载均衡器安装 Kubernetes高可用集群二进制部署&#xff08;二&#xff09;ETCD集群部署 Kubernetes高可用集群二进制部署&#xff08;三&#xff09;部署…

LeetCode 27题:移除元素

题目 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长…

07 Ubuntu中使用poetry工具管理python环境——巨详细!!!

由于conda和ros2的环境实在太容易冲突了。我真的不敢再使用conda&#xff0c;着实是有些搞不明白这解释器之间的关系。 conda的卸载和ros2的安装暂不赘述&#xff0c;下面着重来说如何在Ubuntu中使用poetry进行包管理及遇到的问题。 1 安装poetry 由于在有写入权限的限制&am…

STM32--GPIO

文章目录 GPIO简介GPIO的基本结构GPIO位结构GPIO模式LED和蜂鸣器LED闪烁工程及程序原码代码&#xff1a; 蜂鸣器工程和程序原码代码 传感器光敏传感器控制蜂鸣器工程代码 GPIO简介 GPIO&#xff08;General Purpose Input Output&#xff09;是通用输入/输出口的简称。它是一种…

GO学习之 函数(Function)

GO系列 1、GO学习之Hello World 2、GO学习之入门语法 3、GO学习之切片操作 4、GO学习之 Map 操作 5、GO学习之 结构体 操作 6、GO学习之 通道(Channel) 7、GO学习之 多线程(goroutine) 8、GO学习之 函数(Function) 9、GO学习之 接口(Interface) 文章目录 GO系列前言一、什么是…

UNITY3D 虚拟数字人方向,动捕设备测评 VDSuit-Full

我们成功的用它做了线下演出活动。 开发测试视频 VDSuit-Full动捕开发 分别说优点和不足 优点&#xff1a; 人工技术答疑及时 有厂家解答各种疑难杂症&#xff08;工作日一般1小时就得到回复&#xff09; 比如穿戴&#xff0c;使用方法&#xff0c;限制等。 动作整体捕捉效果较…

【使用内网穿透从公网对本地内网Web服务器访问】

公网访问本地内网web服务器【内网穿透】 文章目录 公网访问本地内网web服务器【内网穿透】前言1. 首先安装PHPStudy2.下载一个开源的网页文件3. 选择“创建网站”并将网页内容指向下载好的开源网页文件4. 打开本地网页5. 打开本地cpolar客户端6. 保存隧道设置 生成数据隧道 前言…

SpringCloud深度学习(在更)

微服务简介 微服务是什么&#xff1f; 微服务是一种架构风格&#xff0c;将一个大型应用程序拆分为一组小型、自治的服务。每个服务都运行在自己独立的进程中&#xff0c;使用轻量级的通信机制&#xff08;通常是HTTP或消息队列&#xff09;进行相互之间的通信。这种方式使得…

如何恢复已删除的 PDF 文件 - Windows 11、10

在传输数据或共享专业文档时&#xff0c;大多数人依赖PDF文件格式&#xff0c;但很少知道如何恢复意外删除或丢失的PDF文件。这篇文章旨在解释如何有效地恢复 PDF 文件。如果您身边有合适的数据恢复工具&#xff0c;PDF 恢复并不像看起来那么复杂。 便携式文档格式&#xff08…

栈和队列的实现

Lei宝啊&#xff1a;个人主页&#xff08;也许有你想看的&#xff09; 愿所有美好不期而遇 前言 &#xff1a; 栈和队列的实现与链表的实现很相似&#xff0c;新瓶装旧酒&#xff0c;没什么新东西。 可以参考这篇文章&#xff1a; -------------------------无头单向不循环…

D. Productive Meeting

Example input 8 2 2 3 3 1 2 3 4 1 2 3 4 3 0 0 2 2 6 2 3 0 0 2 5 8 2 0 1 1 5 0 1 0 0 6 output 2 1 2 1 2 3 1 3 2 3 2 3 5 1 3 2 4 2 4 3 4 3 4 0 2 1 2 1 2 0 4 1 2 1 5 1 4 1 2 1 5 2 解析&#xff1a; 贪心&#xff0c;每次选择两个剩余次数最多的人&#xff0c;并…

ad+硬件每日学习十个知识点(24)23.8.4(时序约束,SignalTap Ⅱ)

文章目录 1.建立时间和保持时间2.为什么要建立时序约束&#xff1f;3.SignalTap Ⅱ4.SignalTap Ⅱ使用方法5.HDL的仿真软件&#xff08;modelsim&#xff09;6.阻抗匹配 1.建立时间和保持时间 答&#xff1a; 2.为什么要建立时序约束&#xff1f; 答&#xff1a; 3.Sign…

火力全开!百度文心3.5三大维度、20项指标国内问鼎!

近日&#xff0c;清华大学新闻与传播学院沈阳团队发布《大语言模型综合性能评估报告》&#xff08;下文简称“报告”&#xff09;&#xff0c;报告显示百度文心一言在三大维度20项指标中综合评分国内第一&#xff0c;超越ChatGPT&#xff0c;其中中文语义理解排名第一&#xff…

深度学习——全维度动态卷积ODConv

ODConv(OMNI-DIMENSIONAL DYNAMIC CONVOLUTION)是一种关注了空域、输入通道、输出通道等维度上的动态性的卷积方法&#xff0c;因此被称为全维度动态卷积。 part1. 什么是动态卷积 动态卷积就是对卷积核进行线性加权 第一篇提出动态卷积的文章也是在SE之后&#xff0c;他提出…

14.2.2 【Linux】software, hardware RAID

磁盘阵列分为硬件与软件。所谓的硬件磁盘阵列是通过磁盘阵列卡来达成阵列的目的。磁盘阵列卡上面有一块专门的芯片在处理 RAID 的任务&#xff0c;因此在性能方面会比较好。在很多任务 &#xff08;例如 RAID 5 的同位检查码计算&#xff09; 磁盘阵列并不会重复消耗原本系统的…