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

树上任意两点的距离

题目描述
给出 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 个点的一棵树&#xff0c;多次询问两点之间的最短距离。 注意&#xff1a;边是双向的。 输入描述 第一行为两个整数 n 和 m。n 表示点数&#xff0c;m 表示询问次数&#xff1b; 下来 n−1 行&#xff0c;每行三个整数 x,y,k&#xff0c;表示点 x 和点 y 之间…...

【 thinkphp8 】00008 thinkphp8数据查询,常用table,name方法,进行数据查询汇总

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 【 t…...

Git的命令合集

关于Git的一些命令合集&#xff0c;会慢慢更新&#xff01; 20241024程序员节开始写的&#xff0c;记录一下~~ git查看log、查看详细提交记录 会显示之前的提交记录 , 排序由近及远 git log log按q退出 git回退到某个commit命令&#xff1a; 退到/进到指定commit的sha码&…...

博客搭建之路:hexo搜索引擎收录

文章目录 hexo搜索引擎收录以百度为例 hexo搜索引擎收录 hexo版本5.0.2 npm版本6.14.7 next版本7.8.0 写博客的目的肯定不是就只有自己能看到&#xff0c;想让更多的人看到就需要可以让搜索引擎来收录对应的文章。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

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《PostgreSQL数据库内核分析》 2、参考书籍&#xff1a;《数据库事务处理的艺术&#xff1a;事务管理与并发控制》 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)

原文标题&#xff1a;Domain Adaptive YOLO for One-Stage Cross-Domain Detection 中文标题&#xff1a;面向单阶段跨域检测的域自适应YOLO 1、Abstract 域转移是目标检测器在实际应用中推广的主要挑战。两级检测器的域自适应新兴技术有助于解决这个问题。然而&#xff0c;两级…...

面试题:描述在前端开发中,如何利用数据结构来优化页面渲染性能,并给出一个具体的示例。

在前端开发中&#xff0c;优化页面渲染性能是提升用户体验的关键之一。合理地使用数据结构可以有效地减少DOM操作的次数、提高数据处理的效率&#xff0c;从而加快页面的渲染速度。以下是一些策略&#xff0c;并给出一个具体的示例。 1. 使用合适的数据结构 数组与对象&#…...

微积分复习笔记 Calculus Volume 1 - 3.2 he Derivative as a Function

3.2 The Derivative as a Function - Calculus Volume 1 | OpenStax...

html 轮播图效果

轮播效果&#xff1a; 1、鼠标没有移入到banner,自动轮播 2、鼠标移入&#xff1a;取消自动轮播、移除开始自动轮播 3、点击指示点开始轮播到对应位置 4、点击前一个后一个按钮&#xff0c;轮播到上一个下一个图片 注意 最后一个图片无缝滚动&#xff0c;就是先克隆第一个图片…...

Android Room(SQLite) too many SQL variables异常

SQLiteException 一、解决办法1. 修改数据库语句2. 分批执行 二、问题根源 转载请注明出处: https://blog.csdn.net/hx7013/article/details/143198862 在使用 Room 或其他基于 SQLite 的 ORM 框架时&#xff0c;批量操作如 IN 或 NOT IN 查询可能会触发 android.database.sqli…...

sentinel原理源码分析系列(八)-熔断

限流为了防止过度使用资源造成系统不稳&#xff0c;熔断是为了识别出”坏”资源&#xff0c;避免好的资源受牵连(雪崩效应)&#xff0c;是保证系统稳定性的关键&#xff0c;也是资源有效使用的关键&#xff0c;sentinel熔断插槽名称Degrade(降级)&#xff0c;本人觉得应该改为熔…...

安全见闻(4)——开阔眼界,不做井底之蛙

内容预览 ≧∀≦ゞ 安全见闻四&#xff1a;操作系统安全机制深度解析声明操作系统机制1. 注册表2. 防火墙3. 自启动与计划任务4. 事件日志5. 内核驱动与设备驱动6. 系统服务7. 进程与线程8. 系统编程 从操作系统机制看病毒设计1. 自启动&#xff1a;病毒如何在系统启动时运行&a…...

(二十二)、k8s 中的关键概念

文章目录 1、总体概览2、第一层&#xff1a;物理机、集群、Node、Pod 之间的关系2、第二层&#xff1a;命名空间 Namespace3、定义4、控制平面&#xff08;Control Plane&#xff09;5、特别的概念 Service6、Deployment 经过 之前几篇文章对 k8s 的实践&#xff0c;结合实践&…...

python基础综合案例(数据可视化-地图可视化)

1.基础地图使用 注意写名字的时候要写全名&#xff0c;比如上海市不能写出上海&#xff0c;不然看不到数据 鼠标点击即可看到数据 设置属性的时候不要忘记导包 # 演示地图可视化的基础使用 from pyecharts.charts import Map from pyecharts.options import VisualMapOpts # 准…...

基于SpringBoot足球场在线预约系统的设计与实现

&#x1f497;博主介绍&#x1f497;&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示&#xff1a;文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…...

操作系统笔记(二)进程,系统调用,I/O设备

什么是进程? 一个正在执行的程序一个包含运行一个程序所需要的所有信息的容器进程的信息保存在一个进程表中( Process Table)。进程表中的每一项对应一个进程,称为进程控制块(Process control block,PCB)。 PCB信息包括: 用户ID(UID)、进程ID(PID)…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

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;用于图像分割或平滑处理。 该函数将输入图像中的…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...