树上任意两点的距离
题目描述
给出 n 个点的一棵树,多次询问两点之间的最短距离。
注意:边是双向的。
输入描述
第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;
下来 n−1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间存在一条边长度为 k;
再接下来 m 行,每行两个整数 x,y,表示询问点 x 到点 y 的最短距离。
输出描述
输出 m 行。对于每次询问,输出一行。
样例输入
2 2
1 2 100
1 2
2 1
样例输出
100
100
对于全部数据,2≤ n n n≤ 1 0 4 10^4 104,1≤ m m m≤ 2 × 1 0 4 2×10^4 2×104,0< k k k≤ 100 100 100,1≤ x , y x,y x,y≤ n n n
首先这道题肯定是不能直接暴力跑的
但是换一个角度想,这是一棵树,先画个图:

比如说我们要求3到4的距离:
1,我们先找出3和4的公共祖先——2
2,把3的深度与4的深度加起来
3,减去重复的部分(根节点到最近公共祖先)

求任意两点的距离大概就是这个思路
然后来看一个重要的数组—— f f f数组
f [ i ] f[i] f[i]表示的是节点 i i i的祖先节点
f i n d ( ) find() find()函数的作用就是找到祖先节点
后面就是dfs遍历节点同时找最近公共祖先
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
struct node{int to,dis;
};
vector<node>a[N];
struct nod{int to,num;
};
vector<nod>q[N];
int n,m;
int vis[N],dis[N],res[N],f[N];
int find(int x){//找祖先函数if(f[x]!=x)f[x]=find(f[x]);return f[x];
}
void dfs(int x){vis[x]=1;for(int i=0;i<a[x].size();i++){//最近的公共祖先肯定要是最短路int v=a[x][i].to;int w=a[x][i].dis;if(vis[v]==0){dis[v]=dis[x]+w;dfs(v);f[v]=x;}}for(int i=0;i<q[x].size();i++){int to=q[x][i].to;int num=q[x][i].num;if(vis[to]==2){res[num]=dis[x]+dis[to]-2*dis[find(to)];//计算距离}}vis[x]=2;
}
signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);a[u].push_back(node{v,w});a[v].push_back(node{u,w});}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);q[x].push_back(nod{y,i});q[y].push_back(nod{x,i});}dfs(1);for(int i=1;i<=m;i++)printf("%d\n",res[i]);//离线输出
}
最后,祝程序员们节日快乐
……祝方昳杨生日快乐……
还有……
对不起……
相关文章:
树上任意两点的距离
题目描述 给出 n 个点的一棵树,多次询问两点之间的最短距离。 注意:边是双向的。 输入描述 第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数; 下来 n−1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间…...
【 thinkphp8 】00008 thinkphp8数据查询,常用table,name方法,进行数据查询汇总
前言:哈喽,大家好,今天给大家分享一篇文章!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏关注哦 💕 目录 【 t…...
Git的命令合集
关于Git的一些命令合集,会慢慢更新! 20241024程序员节开始写的,记录一下~~ git查看log、查看详细提交记录 会显示之前的提交记录 , 排序由近及远 git log log按q退出 git回退到某个commit命令: 退到/进到指定commit的sha码&…...
博客搭建之路:hexo搜索引擎收录
文章目录 hexo搜索引擎收录以百度为例 hexo搜索引擎收录 hexo版本5.0.2 npm版本6.14.7 next版本7.8.0 写博客的目的肯定不是就只有自己能看到,想让更多的人看到就需要可以让搜索引擎来收录对应的文章。hexo支持生成站点地图sitemap 在hexo下的_config.yml中配置站点…...
创建Windows系统还原点
系统保护...
Linux等保测评需要用到的命令
三权设置 查看账户情况 cd /home/ ll 设置审计账户 useradd shenji passwd shenji 修改密码 passwd新密码 设置管理账户 useradd guanli passwd guanli compgen -u 查看用户 切换到root账户 su root 设置审计用户权限 vim /etc/sudoers shenji ALL (root) NOPASSWD:…...
PostgreSQL的学习心得和知识总结(一百五十六)|auto_explain — log execution plans of slow queries
目录结构 注:提前言明 本文借鉴了以下博主、书籍或网站的内容,其列表如下: 1、参考书籍:《PostgreSQL数据库内核分析》 2、参考书籍:《数据库事务处理的艺术:事务管理与并发控制》 3、PostgreSQL数据库仓库…...
数据结构模板代码合集(不完整)
P3368 【模板】树状数组 2 #include <bits/stdc.h> using namespace std; const int maxn 5e5 7;int n, m, s, t; int ans; int a[maxn]; struct node{int l, r;int num; }tr[maxn * 4];void build(int p, int l, int r){tr[p] {l, r, 0};if(l r){tr[p].num a[l];r…...
shell脚本语法详解
目录 shell语法基础 指定shell解析器 注释 运行 变量 定义变量 引用变量 清除变量值 从键盘获取值 输入单值 添加输入提示语 读取多值 编辑 定义只读变量 环境变量 设置环境变量与查看环境变量 特殊变量 三种引号的作用与区别 小括号与大括号 参数传递 位…...
2021亚洲机器学习会议:面向单阶段跨域检测的域自适应YOLO(ACML2021)
原文标题:Domain Adaptive YOLO for One-Stage Cross-Domain Detection 中文标题:面向单阶段跨域检测的域自适应YOLO 1、Abstract 域转移是目标检测器在实际应用中推广的主要挑战。两级检测器的域自适应新兴技术有助于解决这个问题。然而,两级…...
面试题:描述在前端开发中,如何利用数据结构来优化页面渲染性能,并给出一个具体的示例。
在前端开发中,优化页面渲染性能是提升用户体验的关键之一。合理地使用数据结构可以有效地减少DOM操作的次数、提高数据处理的效率,从而加快页面的渲染速度。以下是一些策略,并给出一个具体的示例。 1. 使用合适的数据结构 数组与对象&#…...
微积分复习笔记 Calculus Volume 1 - 3.2 he Derivative as a Function
3.2 The Derivative as a Function - Calculus Volume 1 | OpenStax...
html 轮播图效果
轮播效果: 1、鼠标没有移入到banner,自动轮播 2、鼠标移入:取消自动轮播、移除开始自动轮播 3、点击指示点开始轮播到对应位置 4、点击前一个后一个按钮,轮播到上一个下一个图片 注意 最后一个图片无缝滚动,就是先克隆第一个图片…...
Android Room(SQLite) too many SQL variables异常
SQLiteException 一、解决办法1. 修改数据库语句2. 分批执行 二、问题根源 转载请注明出处: https://blog.csdn.net/hx7013/article/details/143198862 在使用 Room 或其他基于 SQLite 的 ORM 框架时,批量操作如 IN 或 NOT IN 查询可能会触发 android.database.sqli…...
sentinel原理源码分析系列(八)-熔断
限流为了防止过度使用资源造成系统不稳,熔断是为了识别出”坏”资源,避免好的资源受牵连(雪崩效应),是保证系统稳定性的关键,也是资源有效使用的关键,sentinel熔断插槽名称Degrade(降级),本人觉得应该改为熔…...
安全见闻(4)——开阔眼界,不做井底之蛙
内容预览 ≧∀≦ゞ 安全见闻四:操作系统安全机制深度解析声明操作系统机制1. 注册表2. 防火墙3. 自启动与计划任务4. 事件日志5. 内核驱动与设备驱动6. 系统服务7. 进程与线程8. 系统编程 从操作系统机制看病毒设计1. 自启动:病毒如何在系统启动时运行&a…...
(二十二)、k8s 中的关键概念
文章目录 1、总体概览2、第一层:物理机、集群、Node、Pod 之间的关系2、第二层:命名空间 Namespace3、定义4、控制平面(Control Plane)5、特别的概念 Service6、Deployment 经过 之前几篇文章对 k8s 的实践,结合实践&…...
python基础综合案例(数据可视化-地图可视化)
1.基础地图使用 注意写名字的时候要写全名,比如上海市不能写出上海,不然看不到数据 鼠标点击即可看到数据 设置属性的时候不要忘记导包 # 演示地图可视化的基础使用 from pyecharts.charts import Map from pyecharts.options import VisualMapOpts # 准…...
基于SpringBoot足球场在线预约系统的设计与实现
💗博主介绍💗:✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示:文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…...
操作系统笔记(二)进程,系统调用,I/O设备
什么是进程? 一个正在执行的程序一个包含运行一个程序所需要的所有信息的容器进程的信息保存在一个进程表中( Process Table)。进程表中的每一项对应一个进程,称为进程控制块(Process control block,PCB)。 PCB信息包括: 用户ID(UID)、进程ID(PID)…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
