当前位置: 首页 > 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)…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

设计模式和设计原则回顾

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

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...