树上任意两点的距离
题目描述
给出 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)…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
