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

洛谷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++

题目链接&#xff1a;P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态 1.题目解析 1&#xff1a;从8走向6的最短路径&#xff0c;向根节点就是向上走&#xff0c;从8到1会经过三条边&#xff0c;向叶节点就是向下走&#xff0c;从1走到6需要经过两条边&#xff0c…...

《Foundation 起步》

《Foundation 起步》 引言 Foundation 是一个广泛使用的开源前端框架,由 ZURB 团队创建。它旨在帮助开发者构建响应式、可访问性和移动优先的网页。本文将为您提供一个全面的指南,帮助您从零开始学习并使用 Foundation。 Foundation 简介 什么是 Foundation? Foundatio…...

【hot100】刷题记录(6)-轮转数组

题目描述&#xff1a; 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 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生成马赛克/高斯模糊&#xff08;毛玻璃&#xff09;对比&#xff0c;Kotlin import android.graphics.Bitmap import android.graphics.BitmapFactory import android.graphics.Canvas import android.graphics.RectF …...

ThinkPad E480安装Ubuntu 18.04无线网卡驱动

个人博客地址&#xff1a;ThinkPad E480安装Ubuntu 18.04无线网卡驱动 | 一张假钞的真实世界 遗憾的是虽然下面的方法可以解决&#xff0c;但是内核升级后需要重新安装。 基本信息 Ubuntu 18.04ThinkPad E480使用下面的命令查看 Linux 内核&#xff1a; $ uname -r 5.0.0-3…...

自然语言处理——从原理、经典模型到应用

1. 概述 自然语言处理&#xff08;Natural Language Processing&#xff0c;NLP&#xff09;是一门借助计算机技术研究人类语言的科学&#xff0c;是人工智能领域的一个分支&#xff0c;旨在让计算机理解、生成和处理人类语言。其核心任务是将非结构化的自然语言转换为机器可以…...

Ollama 运行从 ModelScope 下载的 GGUF 格式的模型

本文系统环境 Windows 10 Ollama 0.5.7 Ollama 是什么&#xff1f; Ollama 可以让你快速集成和部署本地 AI 模型。它支持各种不同的 AI 模型&#xff0c;并允许用户通过简单的 API 进行调用 Ollama 的安装 Ollama 官网 有其下载及安装方法&#xff0c;非常简便 但如果希…...

Haproxy介绍及学习

一、负载均衡(load balance)&#xff1a; 1.一种服务基于硬件设备实现的高可用反向代理技术&#xff0c;将特定的业务分担给指定的一个或者多个后端特定的服务器&#xff0c;提高了业务的并发处理能力保证业务的高可用并方便对业务后期的水平动态扩展性。 2.使用负载均衡的原因…...

【2024年华为OD机试】 (C卷,200分)- 贪心歌手(JavaScriptJava PythonC/C++)

一、问题描述 问题描述 一个歌手需要从A城前往B城参加演出&#xff0c;必须在T天内到达。途中会经过N座城市&#xff0c;且不能往回走。每两座城市之间的行程天数已知。歌手在每座城市都可以卖唱赚钱&#xff0c;但收入会随着停留天数的增加而递减。具体来说&#xff0c;第一…...

深度学习在金融风控中的应用:突破传统模型的瓶颈

深度学习在金融风控中的应用:突破传统模型的瓶颈 金融风险控制(简称“风控”)是现代金融体系中至关重要的一环,关系到金融机构的稳定性、客户的安全以及整体经济的健康运行。近年来,随着深度学习的迅猛发展,传统的风控模型正面临被颠覆的挑战,新的技术手段和思维方式正…...

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. 也进行了模型切断&#xff0c;用拉普拉斯算子找到最清晰的一帧作为训练的起始 训练了不同的模型去选择数据&#xff0c;比如用Dover去选择美观度比较好的数据&#xff0c…...

开发、科研工具汇总

一些基础教程网站 W3&#xff1a;w3school 在线教程 菜鸟&#xff1a;菜鸟教程 - 学的不仅是技术&#xff0c;更是梦想&#xff01; 开发相关参考文档 Vue2&#xff1a;Vue.js Vue3&#xff1a;Vue.js - 渐进式 JavaScript 框架 | Vue.js MDN&#xff1a;MDN Web Docs HT…...

项目部署(springboot项目)

1、安装Nginx&#xff0c;并开启 2、前端项目打包&#xff1a;npm run build:prod--->dist 3、后端项目打包&#xff1a;install--->xxx.jar 4、开放需要的端口号&#xff1a;比如我的后端项目端口号为8282&#xff0c;则需要防火墙和服务器同时开发8282端口 5、将di…...

OpenEuler学习笔记(十四):在OpenEuler上搭建.NET运行环境

一、在OpenEuler上搭建.NET运行环境 基于包管理器安装 添加Microsoft软件源&#xff1a;运行命令sudo rpm -Uvh https://packages.microsoft.com/config/centos/8/packages-microsoft-prod.rpm&#xff0c;将Microsoft软件源添加到系统中&#xff0c;以便后续能够从该源安装.…...

神经网络的通俗介绍

人工神经网络&#xff0c;是一种模仿人类大脑工作原理的数学模型。人类的大脑是由无数的小“工作站”组成的&#xff0c;每个工作站叫做“神经元”。这些神经元通过“电线”互相连接&#xff0c;负责接收、处理和传递信息。 一、人类大脑神经网络 人类大脑的神经网络大概长这…...

基于 AWS SageMaker 对 DeepSeek-R1-Distilled-Llama-8B 模型的精调与实践

在当今人工智能蓬勃发展的时代&#xff0c;语言模型的性能优化和定制化成为研究与应用的关键方向。本文聚焦于 AWS SageMaker 平台上对 DeepSeek-R1-Distilled-Llama-8B 模型的精调实践&#xff0c;详细探讨这一过程中的技术细节、操作步骤以及实践价值。 一、实验背景与目标 …...

如何使用DeepSeek R1

以下是如何使用DeepSeek R1的详细步骤&#xff1a; ### 一、注册DeepSeek账户 1. **访问官方网站**&#xff1a; - 打开浏览器&#xff0c;访问[chat.deepseek.com](http://chat.deepseek.com)。 2. **注册账户**&#xff1a; - 使用电子邮件、Google账户或86手机号码…...

大屏 UI 设计风格的未来趋势

在科技飞速革新的时代&#xff0c;大屏设备的应用领域不断拓展&#xff0c;从城市的智能交通指挥中心&#xff0c;到商场的互动广告大屏&#xff0c;再到家庭的超大尺寸智能电视&#xff0c;大屏已然成为信息展示与交互的关键载体。大屏 UI 设计风格也随之不断演变&#xff0c;…...

unity学习22:Application类其他功能

目录 1 是否允许后台运行 1.1 Application.runInBackground&#xff0c;显示是否允许后台运行 1.2 设置的地方 2 打开URL 2.1 Application.OpenURL("") 打开超链接 3 退出游戏 3.1 Application.Quit() 退出游戏 4 场景相关 5 返回游戏状态 6 控制游戏的行…...

AT命令驱动的跨平台嵌入式Web服务器框架

1. 项目概述ESP8266_AT_WebServer 是一个面向嵌入式硬件工程师的轻量级、跨平台 Web 服务框架&#xff0c;其核心设计哲学是“硬件无关性”与“协议抽象化”。它并非直接运行于 ESP8266/ESP32 芯片之上&#xff0c;而是将这些 Wi-Fi 模块降级为一个标准的 AT 命令外设&#xff…...

提升开发效率:IntelliJ IDEA必备插件推荐与安装指南(2023最新版)

2023年IntelliJ IDEA插件生态深度解析&#xff1a;从效率工具到全栈开发支持 JetBrains家族的IntelliJ IDEA早已超越普通代码编辑器的范畴&#xff0c;成为现代开发者手中的瑞士军刀。但鲜有人意识到&#xff0c;真正让这把军刀所向披靡的&#xff0c;是背后超过5000个官方认证…...

实战演练:基于快马与豆包开放平台,快速开发智能邮件处理助手

今天想和大家分享一个实战项目&#xff1a;基于豆包开放平台的智能邮件助手开发过程。这个工具特别适合需要频繁处理邮件的职场人士&#xff0c;能自动完成邮件摘要、待办事项提取、回复草拟等重复性工作。 项目背景与需求分析 日常工作中&#xff0c;我们经常要处理大量邮件。…...

如何快速解锁网易云音乐NCM文件:ncmdumpGUI终极指南

如何快速解锁网易云音乐NCM文件&#xff1a;ncmdumpGUI终极指南 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换&#xff0c;Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 还在为网易云音乐下载的NCM格式文件无法在其他…...

ai辅助开发:借助快马平台ai模型打造智能自适应的openclaw chrome数据抓取插件

今天想和大家分享一个最近用AI技术增强网页数据抓取效率的实践——开发一个叫OpenClaw的智能Chrome插件。这个插件的特别之处在于&#xff0c;它不仅能抓取数据&#xff0c;还能通过AI理解网页结构&#xff0c;自动适应不同网站&#xff0c;大大减少了手动编写抓取规则的工作量…...

【Matlab】MATLAB教程:图形属性修改(案例:set(h,‘Color‘,‘red‘),应用:自定义图形样式)

MATLAB教程:图形属性修改(案例:set(h,Color,red),应用:自定义图形样式) 在MATLAB数据可视化、实验报告绘图、工程结果展示等场景中,默认绘制的图形往往难以满足个性化需求和规范要求。无论是调整线条颜色、粗细,还是优化坐标轴、图例样式,核心目标都是通过图形属性修…...

为什么自动驾驶地铁离不开形式化方法?从法国B方法到上海15号线的实战解析

数学如何为自动驾驶地铁筑起安全屏障&#xff1a;从B方法到工业级验证的深度实践 当一列无人驾驶的地铁以80公里时速穿越隧道时&#xff0c;系统每毫秒需要处理200传感器信号、执行30余项控制决策。巴黎地铁14号线自1998年开通以来保持零重大事故记录&#xff0c;上海15号线全自…...

4步完成Axure本地化设置:让新手轻松上手的中文界面方案

4步完成Axure本地化设置&#xff1a;让新手轻松上手的中文界面方案 【免费下载链接】axure-cn Chinese language file for Axure RP. Axure RP 简体中文语言包&#xff0c;不定期更新。支持 Axure 9、Axure 10。 项目地址: https://gitcode.com/gh_mirrors/ax/axure-cn …...

AI模型版本控制:Git for ML最佳实践

当软件测试遇上AI模型迭代对于软件测试从业者而言&#xff0c;版本控制是保障软件质量、实现可追溯性的基石。然而&#xff0c;当测试对象从传统的功能模块转变为动态演进的AI模型时&#xff0c;版本管理的复杂性陡然增加。一个推荐模型本周表现优异&#xff0c;下周却因数据漂…...

VSCode本地历史记录插件Local History保姆级教程:从安装到.gitignore配置

VSCode本地历史记录插件Local History深度指南&#xff1a;从高效使用到项目集成 为什么开发者需要本地历史记录功能 在日常开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;修改了一段代码后突然意识到之前的版本可能更好&#xff0c;或者不小心覆盖了重要内容却无法撤…...