洛谷P3884 [JLOI2009] 二叉树问题(详解)c++
题目链接:P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态

1.题目解析
1:从8走向6的最短路径,向根节点就是向上走,从8到1会经过三条边,向叶节点就是向下走,从1走到6需要经过两条边,再用向上的边数×2+向下的边数,所以是3*2+2,所以8到6的距离是8,我们可以发现8到6的距离和6到8的距离是不一样的,8到6是8,6到8是7

2:这道题跟二叉树没什么关系,如果他告诉我们的是树上一条边一条边的形式来让我们建图的话,我们并不知道左右节点,我们都不知道左右节点那该怎么还原二叉树,所以这道题的名字,虽然是二叉树问题,本质上他跟二叉树没什么关系,他如果告诉我们的是u,v表示树上存在一条连接u,v的边这样的信息的话,就不能用二叉树的方式来存储它了,因为我们不知道左右节点,所以我们要不就用链式前向星,要不用vecrot数组,用存树的方式来存这
3:存的时候只用u指向v的这条边就行了,不用存v指向u,他给了我们两条边,我们本来不清楚谁是父亲谁是孩子,但这道题已经保证了u是v的父亲
2.讲解算法原理
1.建树 - vector数组
const int N = 110;
int n;
vector<int> edges[N]; //存树int main()
{cin >> n;for (int i = 1; i < n; ++i){int u, v; cin >> u >> v;//u -> vedges[u].push_back(v);}return 0;
}
2.求树的深度(高度):树高=max(子树的高度)+1
当我们站在根节点的角度求深度的时候,你只要告诉我左子树以及右子树这两颗子树的深度比较出来的最大值,再加1返回就行(树高=max(子树的高度)+1),如何求子树的高度?我们发现子树本身还是一个树,就可以继续套用这个公式(树高=max(子树的高度)+1),就可以用递归来实现求深度
int dfs(int u)
{int ret = 0;for (auto v : edges[u]){ret = max(ret, dfs(v));}return ret + 1;
}
3.树的宽度:借助bfs过程,每次入队出队一层、
树的宽度和一层一层有关系,如果涉及一层一层的话,用bfs比较好解,因为用bfs,每次循环就是把一层加入到队列里面
int bfs()
{queue<int> q;q.push(1);int ret = 0;while (q.size()){//记录比较队列元素个数int sz = q.size();ret = max(ret, sz);//把每层孩子加入队列之后循环结束while (sz--){int u = q.front(); q.pop();for (auto v : edges[u]){q.push(v);}}}return ret;
}
4.求x到y到距离:1.先从x向上爬,同时标记路径中,所有的点到 x的距离 2.接下来从y开始向上爬,当第一次遇到标记点时,更新结果

假设我们要求10到7之间的距离,2*2+1=5,我们可以先让10这个点向上爬,并标记向上爬的所有路径,比如10爬到6,就标记6到10之间的距离是1,继续爬到3,标记3到10的距离等于2,爬到1,标记1到10的距离是3,爬到不能再爬的时候停止
当标记完10爬到1的路径之后,让7开始向上爬,7向上爬一个点的时候就发现标记点了,这个路径就是1,刚刚标记的过程中3到10的距离是2,所以2*2+1就是10到7的距离了
1.如何向上爬?
创建数组 int fa[N]; fa[i] 表示 i 这个点的父亲是谁,比如fa[6] = 3,6的父亲就是3

2.如何标记当前点到x的距离
创建数组int dsit[N]; //dist[i] 表示 i 这个点到x的最短距离,让x指向10,如果10有父亲,更新父亲到10的距离,dist[fa[x]] = dist[x] + 1; 更新完后,让x向上移动,x = fa[x];一直重复此过程,直到走到顶

3.如何标记y到相遇点的距离
创建变量 int len = 0;假设刚开始变量y指向7,如果7有父亲,并且当前点不是相遇点就让y往上爬,直到爬到相遇点为止,y = fa[y],len++;直到y走到相遇点为止或是走到不能在走走到1为止,此时len里面就存着y到相遇点的距离
代码实现:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;const int N = 110;
int n;
vector<int> edges[N]; //存树int fa[N]; //fa[i]表示i结点的父亲
int dist[N]; //dist[i]表示i到x的最短距离int dfs(int u)
{int ret = 0;for (auto v : edges[u]){ret = max(ret, dfs(v));}return ret + 1;
}int bfs()
{queue<int> q;q.push(1);int ret = 0;while (q.size()){//记录比较队列元素个数int sz = q.size();ret = max(ret, sz);//把每层孩子加入队列之后循环结束while (sz--){int u = q.front(); q.pop();for (auto v : edges[u]){q.push(v);}}}return ret;
}int main()
{cin >> n;for (int i = 1; i < n; ++i){int u, v; cin >> u >> v;//u -> vedges[u].push_back(v); //孩子v存到各自的父亲u里fa[v] = u; //v的父亲是u}//求深度cout << dfs(1) << endl;//求宽度cout << bfs() << endl;//求距离int x, y; cin >> x >> y;while (x != 1){dist[fa[x]] = dist[x] + 1;x = fa[x];}int len = 0;while (y != 1 && dist[y] == 0) //没经过x经过的点,dist的值为0{len++;y = fa[y];}cout << dist[y] * 2 + len;return 0;
}
相关文章:
洛谷P3884 [JLOI2009] 二叉树问题(详解)c++
题目链接:P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态 1.题目解析 1:从8走向6的最短路径,向根节点就是向上走,从8到1会经过三条边,向叶节点就是向下走,从1走到6需要经过两条边,…...
《Foundation 起步》
《Foundation 起步》 引言 Foundation 是一个广泛使用的开源前端框架,由 ZURB 团队创建。它旨在帮助开发者构建响应式、可访问性和移动优先的网页。本文将为您提供一个全面的指南,帮助您从零开始学习并使用 Foundation。 Foundation 简介 什么是 Foundation? Foundatio…...
【hot100】刷题记录(6)-轮转数组
题目描述: 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转…...
Android createScaledBitmap与Canvas通过RectF drawBitmap生成马赛克/高斯模糊(毛玻璃)对比,Kotlin
Android createScaledBitmap与Canvas通过RectF drawBitmap生成马赛克/高斯模糊(毛玻璃)对比,Kotlin import android.graphics.Bitmap import android.graphics.BitmapFactory import android.graphics.Canvas import android.graphics.RectF …...
ThinkPad E480安装Ubuntu 18.04无线网卡驱动
个人博客地址:ThinkPad E480安装Ubuntu 18.04无线网卡驱动 | 一张假钞的真实世界 遗憾的是虽然下面的方法可以解决,但是内核升级后需要重新安装。 基本信息 Ubuntu 18.04ThinkPad E480使用下面的命令查看 Linux 内核: $ uname -r 5.0.0-3…...
自然语言处理——从原理、经典模型到应用
1. 概述 自然语言处理(Natural Language Processing,NLP)是一门借助计算机技术研究人类语言的科学,是人工智能领域的一个分支,旨在让计算机理解、生成和处理人类语言。其核心任务是将非结构化的自然语言转换为机器可以…...
Ollama 运行从 ModelScope 下载的 GGUF 格式的模型
本文系统环境 Windows 10 Ollama 0.5.7 Ollama 是什么? Ollama 可以让你快速集成和部署本地 AI 模型。它支持各种不同的 AI 模型,并允许用户通过简单的 API 进行调用 Ollama 的安装 Ollama 官网 有其下载及安装方法,非常简便 但如果希…...
Haproxy介绍及学习
一、负载均衡(load balance): 1.一种服务基于硬件设备实现的高可用反向代理技术,将特定的业务分担给指定的一个或者多个后端特定的服务器,提高了业务的并发处理能力保证业务的高可用并方便对业务后期的水平动态扩展性。 2.使用负载均衡的原因…...
【2024年华为OD机试】 (C卷,200分)- 贪心歌手(JavaScriptJava PythonC/C++)
一、问题描述 问题描述 一个歌手需要从A城前往B城参加演出,必须在T天内到达。途中会经过N座城市,且不能往回走。每两座城市之间的行程天数已知。歌手在每座城市都可以卖唱赚钱,但收入会随着停留天数的增加而递减。具体来说,第一…...
深度学习在金融风控中的应用:突破传统模型的瓶颈
深度学习在金融风控中的应用:突破传统模型的瓶颈 金融风险控制(简称“风控”)是现代金融体系中至关重要的一环,关系到金融机构的稳定性、客户的安全以及整体经济的健康运行。近年来,随着深度学习的迅猛发展,传统的风控模型正面临被颠覆的挑战,新的技术手段和思维方式正…...
LLM - 大模型 ScallingLaws 的指导模型设计与实验环境(PLM) 教程(4)
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/145323420 免责声明:本文来源于个人知识与公开资料,仅用于学术交流,欢迎讨论,不支持转载。 Scaling Laws (缩放法则) 是大模型领域中,用于描述 模型性能(Loss) 与…...
hunyuan 混元学习
使用了5个subset,也是用了text-image和text-video进行训练的 也是进行了复杂的视频选择。同movie gen. 也进行了模型切断,用拉普拉斯算子找到最清晰的一帧作为训练的起始 训练了不同的模型去选择数据,比如用Dover去选择美观度比较好的数据,…...
开发、科研工具汇总
一些基础教程网站 W3:w3school 在线教程 菜鸟:菜鸟教程 - 学的不仅是技术,更是梦想! 开发相关参考文档 Vue2:Vue.js Vue3:Vue.js - 渐进式 JavaScript 框架 | Vue.js MDN:MDN Web Docs HT…...
项目部署(springboot项目)
1、安装Nginx,并开启 2、前端项目打包:npm run build:prod--->dist 3、后端项目打包:install--->xxx.jar 4、开放需要的端口号:比如我的后端项目端口号为8282,则需要防火墙和服务器同时开发8282端口 5、将di…...
OpenEuler学习笔记(十四):在OpenEuler上搭建.NET运行环境
一、在OpenEuler上搭建.NET运行环境 基于包管理器安装 添加Microsoft软件源:运行命令sudo rpm -Uvh https://packages.microsoft.com/config/centos/8/packages-microsoft-prod.rpm,将Microsoft软件源添加到系统中,以便后续能够从该源安装.…...
神经网络的通俗介绍
人工神经网络,是一种模仿人类大脑工作原理的数学模型。人类的大脑是由无数的小“工作站”组成的,每个工作站叫做“神经元”。这些神经元通过“电线”互相连接,负责接收、处理和传递信息。 一、人类大脑神经网络 人类大脑的神经网络大概长这…...
基于 AWS SageMaker 对 DeepSeek-R1-Distilled-Llama-8B 模型的精调与实践
在当今人工智能蓬勃发展的时代,语言模型的性能优化和定制化成为研究与应用的关键方向。本文聚焦于 AWS SageMaker 平台上对 DeepSeek-R1-Distilled-Llama-8B 模型的精调实践,详细探讨这一过程中的技术细节、操作步骤以及实践价值。 一、实验背景与目标 …...
如何使用DeepSeek R1
以下是如何使用DeepSeek R1的详细步骤: ### 一、注册DeepSeek账户 1. **访问官方网站**: - 打开浏览器,访问[chat.deepseek.com](http://chat.deepseek.com)。 2. **注册账户**: - 使用电子邮件、Google账户或86手机号码…...
大屏 UI 设计风格的未来趋势
在科技飞速革新的时代,大屏设备的应用领域不断拓展,从城市的智能交通指挥中心,到商场的互动广告大屏,再到家庭的超大尺寸智能电视,大屏已然成为信息展示与交互的关键载体。大屏 UI 设计风格也随之不断演变,…...
unity学习22:Application类其他功能
目录 1 是否允许后台运行 1.1 Application.runInBackground,显示是否允许后台运行 1.2 设置的地方 2 打开URL 2.1 Application.OpenURL("") 打开超链接 3 退出游戏 3.1 Application.Quit() 退出游戏 4 场景相关 5 返回游戏状态 6 控制游戏的行…...
OpenClaw开源项目深度体验:对比其与星图GPU平台Qwen3-14B-Int4-AWQ部署差异
OpenClaw开源项目深度体验:对比其与星图GPU平台Qwen3-14B-Int4-AWQ部署差异 1. 项目概览与核心功能 OpenClaw是近期备受关注的开源大模型项目,主打轻量化和易部署特性。它采用混合专家架构(MoE),在保持模型性能的同时显著降低了计算资源需求…...
Unity资源提取技术解密:AssetRipper效能革命与实战指南
Unity资源提取技术解密:AssetRipper效能革命与实战指南 【免费下载链接】AssetRipper GUI Application to work with engine assets, asset bundles, and serialized files 项目地址: https://gitcode.com/GitHub_Trending/as/AssetRipper 在游戏开发迭代加速…...
解锁3大自由:5分钟掌握的音乐格式解放工具
解锁3大自由:5分钟掌握的音乐格式解放工具 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 在数字音乐时代,我们却常常面临这样的困境:下载的音乐被限制在特定播放器中,就像拥有一本精美…...
如何高效解决网页视频下载难题:VideoDownloadHelper智能解析工具全解析
如何高效解决网页视频下载难题:VideoDownloadHelper智能解析工具全解析 【免费下载链接】VideoDownloadHelper Chrome Extension to Help Download Video for Some Video Sites. 项目地址: https://gitcode.com/gh_mirrors/vi/VideoDownloadHelper 在数字化内…...
鸿蒙与Android双端蓝牙开发避坑指南:定位权限、虚拟地址与厂商SDK那些事
鸿蒙与Android双端蓝牙开发实战:权限策略与真实地址获取全解析 当你的应用需要同时在鸿蒙和Android设备上稳定运行蓝牙功能时,系统差异就像一片雷区——Android 12的权限拆分、鸿蒙4.0的虚拟地址返回、不同版本间的API兼容性,每个环节都可能让…...
SmallThinker-3B-Preview部署教程:边缘设备一键运行的保姆级指南
SmallThinker-3B-Preview部署教程:边缘设备一键运行的保姆级指南 想试试在树莓派或者你的旧笔记本上跑一个自己的AI助手吗?今天要聊的SmallThinker-3B-Preview,可能就是你的菜。它是个小个子,但本事不小,专门为那些内…...
SmolVLA代码审查助手:自动检测C语言基础代码缺陷
SmolVLA代码审查助手:让C语言开发告别低级错误 写C语言代码,最怕什么?不是复杂的算法,也不是深奥的架构,而是那些不起眼却要命的基础错误。一个忘记释放的内存,一个数组越界的访问,或者一个不符…...
s2-proGPU利用率提升方案:批处理合成与异步请求性能压测报告
s2-pro GPU利用率提升方案:批处理合成与异步请求性能压测报告 1. 项目背景与挑战 s2-pro作为Fish Audio开源的专业级语音合成模型镜像,在实际应用中面临GPU利用率不足的问题。通过初步监测发现: 单次请求GPU利用率峰值仅达到35-40%请求间隔…...
从CPU到内存:用74LS74芯片手把手教你搭建一个D边沿触发器(附波形图分析)
从面包板到示波器:用74LS74芯片实战D边沿触发器的完整指南 当你第一次在数字电路课本上看到"D边沿触发器"这个词时,是否感觉它像是一个抽象的黑盒子?教科书上的真值表和波形图虽然精确,但总缺少那么一点"触手可及&…...
Qwen2.5-VL视觉定位模型支持多目标检测:一句话同时定位‘人和汽车’,效果惊艳
Qwen2.5-VL视觉定位模型支持多目标检测:一句话同时定位"人和汽车",效果惊艳 1. 视觉定位技术的新突破 在计算机视觉领域,视觉定位(Visual Grounding)技术正经历着革命性的进步。传统的目标检测方法需要预先…...
