当前位置: 首页 > news >正文

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&#xff1a; 2 2 1 2 100 1 2 2 1输出样例1&#xff1a; 100 100输入样例2&#xff1a; 3 2 1 2 10 3 1 15 1 2 3 2输出样例2&#xff1a; 10 25 #include<bits/stdc.h> using namespace std; typedef long long ll; const int N2e55; int n,m,x,y,k,r…...

JVM-运行时数据区

目录 什么是运行时数据区&#xff1f; 方法区 堆 程序计数器 虚拟机栈 局部变量表 操作数栈 动态连接 运行时常量池 方法返回地址 附加信息 本地方法栈 总结&#xff1a; 什么是运行时数据区&#xff1f; Java虚拟机在执行Java程序时&#xff0c;将它管…...

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. 排序的概念&#xff1a; 2.插入排序基本思想 3.直接插入排序 4.希尔排序 1. 排序的概念&#xff1a; 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xf…...

云计算——ACA学习 云计算概述

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 目录 写在前面 上章回顾 本章简介 本章目标 一.云计算产生背景 1.信息时代的重点变革…...

如何为网站进行全面的整站翻译?

要翻译整个网站&#xff0c;可以按照以下步骤进行&#xff1a; 确定翻译需求&#xff1a;确定你需要将整个网站翻译成哪种语言。这可以根据你的目标受众和市场进行决定。 寻找翻译资源&#xff1a;你可以选择以下几种方式来进行网站翻译&#xff1a; a. 人工翻译&#xff1a;雇…...

项目部署(前后端分离)

1、前端项目 &#xff08;打包成dist文件,放到nginx的html目录下面&#xff09;&#xff0c;然后配置nginx 2、后端项目部署 使用之前的shell脚本&#xff08;然后赋予用户权限&#xff09;&#xff0c;最后运行脚本 查看进程...

增强型Web安全网关在银行的应用

销售&#xff0c;绝不是降低身份去取悦客户&#xff0c;而是像朋友一样给予合理的建议。你刚好需要&#xff0c;我刚好专业&#xff01;仅此而已&#xff01; 乔.吉拉德 健康的安全体系&#xff0c;还可以更完善 浙江某商业银行股份有限公司是一家成立多年的商业银行&#xf…...

Oracle-ORA-00600:[ktspffbmb:objdchk_kcbnew_3]

问题背景: 应用执行存储过程报错ORA-00600: 内部错误代码, 参数: [ktspffbmb:objdchk_kcbnew_3], [0], [3303775], [4], [], [], [], [], [], [], [], []&#xff0c;导致过程无法正常执行 ORA-00600: 内部错误代码, 参数: [ktspffbmb:objdchk_kcbnew_3], [0], [3303775], [4]…...

SPINN:基于设备和云的神经网络协同递进推理

SPINN&#xff1a;基于设备和云的神经网络协同递进推理 论文标题&#xff1a;SPINN: synergistic progressive inference of neural networks over device and cloud 原文链接&#xff1a;https://dl.acm.org/doi/10.1145/3372224.3419194 论文动机 现代CNN过多的计算需求&am…...

数据结构-二叉树

数据结构-二叉树 二叉树的概念二叉树的遍历分类 建立二叉树&#xff0c;并遍历二叉树的最小单元二叉树的最小单元初始化初始化二叉树前序遍历的实现中序遍历的实现后序遍历的实现计算节点的个数计算树的深度求第k层的个数查找二叉树的元素分层遍历 全部代码如下 二叉树的概念 二…...

Open3D 进阶(4)高斯混合点云聚类

目录 一、算法原理1、原理概述2、实现流程3、参考文献二、代码实现三、结果展示四、测试数据本文由CSDN点云侠原创,原文链接。爬虫网站自重。 一、算法原理 1、原理概述 高斯混合聚类(GMM)算法假设数据点是由一个或多个高斯分布生成的,并通过最大似然估计的方法来估计每个簇…...

计算机组成和IO

文章目录 计组和Epoll&#xff1a;计算机组成原理&#xff1a;网络数据接收的流程&#xff1a;内核如何管理socket以及状态的更新select系统调用的复杂度epoll的et和lt模式及java的选择 国内访问chatai就可以 https://aiweb.douguguo.com/?typeadd计组和Epoll&#xff1a; 计…...

STM32CUBUMX配置RS485 modbus STM32(从机)亲测可用

———————————————————————————————————— ⏩ 大家好哇&#xff01;我是小光&#xff0c;嵌入式爱好者&#xff0c;一个想要成为系统架构师的大三学生。 ⏩最近在开发一个STM32H723ZGT6的板子&#xff0c;使用STM32CUBEMX做了很多驱动&#x…...

系统设计类题目汇总

1 设计一个系统统计当前时刻北京用户在线人数 【Redis】位图以及位图的使用场景(统计在线人数和用户在线状态) 1.1 方案一&#xff1a; 在用户登录时&#xff0c;使用 Redis SET 将用户 ID 添加到一个特定的键&#xff08;例如 “online:beijing”&#xff09;。用户退出时&…...

css滚动条样式指南

css滚动条样式指南 滚动条是网页设计中经常被忽视的元素。虽然它看起来像是一个小细节&#xff0c;但它在网站导航中起着至关重要的作用。默认的滚动条可能看起来不合适&#xff0c;有损整体美观。本文将介绍如何使用 CSS 自定义滚动条。 在 Chrome、Edge 和 Safari 中设置滚…...

vue子组件修改父组件传递的变量(自定义日期时间组件,时间间隔为15分钟或者一个小时)

vue子组件修改父组件传递的变量 子组件不能直接修改父组件变量的值&#xff0c;但是可以通过调用父组件的方法来修改。 实现步骤 在父组件声明变量 export default {data() {return {startTime:"",......},......} }在父组件使用子组件并传递数据&#xff0c;修改…...

【PyTorch】nn.Conv2d函数详解

nn.Conv2d 是 PyTorch 中的一个卷积层&#xff0c;用于实现二维卷积操作 torch.nn.Conv2d(in_channels, out_channels, kernel_size, stride1, padding0, dilation1, groups1, biasTrue, padding_modezeros, deviceNone, dtypeNone )参数解释 in_channels&#xff1a;输入的通…...

数智保险 创新未来 | GBASE南大通用亮相中国保险科技应用高峰论坛

本届峰会以“数智保险 创新未来”为主题&#xff0c;GBASE南大通用携新一代创新数据库产品及金融信创解决方案精彩亮相&#xff0c;与国内八百多位保险公司高管和众多保险科技公司技术专家&#xff0c;就保险领域数字化的创新应用及生态建设、新一代技术突破及发展机遇、前沿科…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...