SCAU18923--二叉树的直径
18923 二叉树的直径
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。1/ \2 3/ \ 4 5 答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
输入格式
共n行。 第一行一个整数n，表示有n个结点，编号为1至n。 第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的直径。
输入样例
5 1 2 1 3 2 4 2 5
输出样例
3
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>using namespace std;int n; // 节点总数
vector<int> lch(10001); // 存储每个节点的左孩子，索引代表父节点，值代表左孩子节点编号
vector<int> rch(10001); // 存储每个节点的右孩子，索引代表父节点，值代表右孩子节点编号
vector<int> v(10001); // 记录每个节点作为父节点的出现次数，用于判断左右孩子
int D = 0; // 记录当前找到的最大直径// 递归函数：返回以 u 为根的子树高度，同时更新直径 D
int dfs(int u) {if (u == 0) { // 如果当前节点为空（0表示空节点），返回高度0return 0;}int rlen, llen; // 分别记录左右子树的高度llen = dfs(lch[u]); // 递归计算左子树的高度rlen = dfs(rch[u]); // 递归计算右子树的高度D = max(D, rlen + llen); // 更新最大直径，当前节点的直径是左右子树高度之和return max(rlen, llen) + 1; // 返回当前子树的高度（左右子树中的较大高度 + 1）
}int main() {ios::sync_with_stdio(false); // 关闭同步，提高输入输出速度cin.tie(nullptr); // 解除cin和cout的绑定，进一步提升速度cin >> n; // 读取节点总数// 读取n-1条边，构建二叉树结构for (int i = 1; i < n; i++) {int m, j;cin >> m >> j; // 读取父节点m和子节点jif (v[m] == 0) { // 如果m第一次作为父节点出现，j作为左孩子lch[m] = j;} else { // 否则，j作为右孩子rch[m] = j;}v[m]++; // 增加m作为父节点的出现次数}dfs(1); // 从根节点（假设为1）开始深度优先搜索，计算子树高度并更新直径Dcout << D; // 输出最大直径return 0;
}相关文章：
SCAU18923--二叉树的直径
18923 二叉树的直径 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题 语言: G;GCC Description 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点…...
理解 RESTful 风格：现代 Web 服务的基石
在当今的互联网时代，Web 服务成为了连接各种应用和系统的关键。而 RESTful 风格，作为一种广泛采用的架构风格，为设计和实现 Web 服务提供了一套简洁而强大的指导原则。本文将深入探讨 RESTful 风格的核心概念、优势以及如何在实际项目中应用它…...
大模型（3）——RAG（Retrieval-Augmented Generation，检索增强生成）
文章目录 1. 核心组成2. 工作流程3. 训练方式4. 优势与局限5. 应用场景6. 典型模型变体总结 RAG（Retrieval-Augmented Generation，检索增强生成）是一种结合了信息检索与文本生成的技术，旨在通过引入外部知识库提升生成内容的准确性…...
电子科技大学软件工程实践期末
Java基础 面向对象 Java高级编程 2023： 软件工程基础 ch1软件工程概述 软件的概念和特点 软件危机的概念以及产生的原因 软件工程的定义 三要素 应用软件工程的原因 三要素：工具，方法，过程 ch2 软件过程 软件生命周期 软件过程…...
线上jvm假死问题排查
1.线上告警接口超时 看接口是用户服务，查看nacos服务实例，发现有一个节点已经下线了 3.找到对应节点所在服务器，jps -l 命令发现用户服务还在，初步判断是假死 4.使用 jstat -gc 进程id 1000 每秒打印gc情况，发现频繁…...
Redis中SETNX、Lua 脚本和 Redis事务的对比
在 Redis 中，SETNX、Lua 脚本 和 Redis 事务 都可以用于实现原子性操作，但它们的适用场景和能力范围不同。以下是详细对比和原因分析： 1. SETNX 的原子性与局限性 (1) 原子性保证 SETNX（SET if Not eXists） 是 Redis…...
Nginx配置记录访问信息
文章目录 方法一：使用Nginx原生配置记录访问信息方法二：使用Nginx_headers_more模块记录更加详细的信息 Nginx被广泛应用于各种场景如：Web服务器、反向代理服务器、负载均衡器、Web应用防火墙(WAF)等 在实际的产品开发中，无论是功…...
基于机载激光雷达数据的森林生物量估测：AI驱动的遥感革新
一、技术背景与意义 森林生物量是生态系统碳循环和碳汇估算的核心参数。传统遥感方法（如光学影像）在三维结构解析上存在局限，而机载激光雷达（LiDAR）凭借高精度点云数据，能够捕捉森林的垂直结构信息。结合人…...
Redis中的事务和原子性
在 Redis 中，事务 和 原子性 是两个关键概念，用于保证多个操作的一致性和可靠性。以下是 Redisson 和 Spring Data Redis 在处理原子性操作时的区别与对比： 1. Redis 的原子性机制 Redis 本身通过以下方式保证原子性： 单线程模型…...
SSL证书：谷歌算法排名的安全基石与信任杠杆
一、技术演进：从安全信号到算法基石 谷歌对SSL证书的重视始于2014年，当时HTTPS首次被纳入排名算法信号。经过十年迭代，SSL证书已从“加分项”升级为“基础门槛”。2025年算法更新中，其权重占比达2%，与页面加载速度、移…...
XXX企业云桌面系统建设技术方案书——基于超融合架构的安全高效云办公平台设计与实施
目录 1. 项目背景与目标1.1 背景分析1.2 建设目标2. 需求分析2.1 功能需求用户规模与场景终端兼容性2.2 非功能需求3. 系统架构设计3.1 总体架构图流程图说明3.2 技术选型对比3.3 网络设计带宽规划公式4. 详细实施方案4.1 分阶段部署计划4.2 桌面模板配置4.3 测试方案性能测试工…...
【GESP真题解析】第 18 集 GESP 一级 2024 年 12 月编程题 1：温度转换
大家好，我是莫小特。 这篇文章给大家分享 GESP 一级 2024 年 12 月编程题第 1 题：温度转换。 题目链接 洛谷链接：B4062 温度转换 一、完成输入 根据题意，输入只有一行，为实数，数据范围： 0 &l…...
鸿蒙开发进阶：深入解析ArkTS语言特性与高性能编程实践
一、前言 在鸿蒙生态蓬勃发展的当下，开发者对于高效、优质的应用开发语言需求愈发迫切。ArkTS 作为鸿蒙应用开发的核心语言，在继承 TypeScript 优势的基础上，进行了诸多优化与扩展，为开发者带来了全新的编程体验。本文将深入剖析…...
)
现代计算机图形学Games101入门笔记(十七)
双向路径追踪 外观建模 散射介质 人的头发不能用在动画的毛发上。 动物的髓质Medulla特别大 双层圆柱模型应用 BSSRDF是BRDF的延伸。 天鹅绒用BRDF不合理，转成散射介质。 法线分布 光追很难处理微表面模型 光在微型细节上，光是一个波，会发生衍…...
工单派单应用：5 大核心功能提升协作效率
一、工单管理：全流程一目了然 快速创建：录入任务内容、优先级，从源头明确目标 状态分类：待处理 / 进行中 / 已完成工单一目了然，个人进度随时掌控 灵活分配：公海池抢单机制，成员按能力自主接…...
ｍａｖｅｎ 多个模块之间互相引入加载配置的偶遇问题
因为子项目添加了:<!-- aliyun sms SDK --> <dependency><groupId>com.aliyun</groupId><artifactId>aliyun-java-sdk-core</artifactId><version>4.6.3</version> </dependency>导致原本运行良好的构建模块，…...
【蓝桥杯嵌入式】【模块】五、ADC相关配置及代码模板
1. 前言 最近在准备16届的蓝桥杯嵌入式赛道的国赛，打算出一个系列的博客，记录STM32G431RBT6这块比赛用板上所有模块可能涉及到的所有考点，如果有错误或者遗漏欢迎各位大佬斧正。 本系列博客会分为以下两大类： 1.1. 单独模块的讲…...
DP2 跳台阶【牛客网】
文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 DP2 跳台阶 一、题目描述 二、测试用例 三、解题思路 基本思路： 动态规划题目的难点基本在于构造状态转移方程，对应这题，我们可以发现每次跳跃我…...
KC 喝咖啡/书的复制/奶牛晒衣服/ 切绳子
二分的解题思路： 常解决最小值最大化和最大值最小化问题 步骤解析 确定答案范围 设定初始左边界 left 和右边界 right，确保解在此区间内。例如： 求最小最大值时，left 可取单个元素的最大值，right 取所有元素总和。 …...
Jedis快速入门【springboot】
引入依赖 <dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><version>6.0.0</version> </dependency> 创立jedis对象，建立连接 private Jedis jedis; BeforeEach void setUp(){//1 …...
SpringBoot 商城系统高并发引起的库存超卖库存问题 乐观锁 悲观锁 抢购 商品秒杀 高并发
介绍 在高并发场景下，特别是商品秒杀、抢购等情况下，库存超卖问题是一个常见且棘手的问题。为了解决这个问题，Spring Boot 常使用乐观锁和悲观锁来保证数据的正确性和一致性。 悲观锁 悲观锁假设在多线程或多进程环境中，资源会被…...
[python] 轻量级定时任务调度库schedule使用指北
schedule是一款专为简化定时任务调度而设计的Python库，它通过直观的语法降低了周期性任务的实现门槛。作为进程内调度器，它无需额外守护进程，轻量且无外部依赖，适合快速搭建自动化任务。不过，该库在功能完整性上有所取…...
MySQL：to many connections连接数过多
当你遇到 MySQL: Too many connections 错误时，意味着当前连接数已达到 MySQL 配置的最大限制。这通常是由于并发连接过多或连接未正确关闭导致的。 一、查看当前连接数 查看 MySQL 当前允许的最大连接数 SHOW VARIABLES LIKE max_connections;查看当前使用的最大…...
uthash是一个非常轻量级的库
如大家所知，uthash是一个非常轻量级的库。该库的使用非常简单，无需格外的静态库或动态库，仅需导入目标的头文件即可。 这种配置方式虽然简单，但是使用操作却需要用到大量的宏函数。在使用宏函数时不像使用普通函数一样自由和遍历…...
大模型的开发应用（三）：基于LlaMAFactory的LoRA微调（上）
基于LlaMAFactory的LoRA微调（上） 0 前言1 LoRA微调1 LoRA微调的原理1.2 通过peft库为指定模块添加旁支1.3 lora前后结构输出结果对比1.4 使用PyTorch复现 LoRA.Linear1.5 使用peft进行LoRA微调案例 2 LLaMA-Factory2.1 LLaMA-Factory简介2.2 LLaMA-Facto…...
跨域_Cross-origin resource sharing
同源是指"协议域名端口"三者相同，即便两个不同的域名指向同一个ip,也非同源 1.什么是CORS? CORS是一个W3C标准，全称是"跨域资源共享"（Cross-origin resource sharing）。它允许浏览器向跨源服务器ÿ…...
奥威BI：打破AI数据分析伪场景，赋能企业真实决策价值
在当今企业数字化转型的浪潮中，AI数据分析产品如雨后春笋般涌现，但许多看似创新的功能设计实则难以落地，沦为“伪需求场景”。这些伪场景不仅浪费企业资源，还可能误导决策，阻碍企业数字化转型进程。在此背景下…...
LLaMA-Factory全解析：大模型微调的开源利器与实战指
技术演进背景与核心价值架构设计与关键技术解析环境搭建与工具链配置全流程微调实战指南企业级应用与高级功能性能优化与安全部署未来发展趋势展望1. 技术演进背景与核心价值 1.1 大模型微调的技术痛点 当前开源大模型（如LLaMA、Qwen、Baichuan等）在通用领域表现优异，但垂…...
python-数据可视化（大数据、数据分析、可视化图像、HTML页面）
通过 Python 读取 XLS 、CSV文件中的数据，对数据进行处理，然后生成包含柱状图、扇形图和折线图的 HTML 报告。这个方案使用了 pandas 处理数据，matplotlib 生成图表，并将图表嵌入到 HTML 页面中。 1.XSL文件生成可视化图像、生成h…...
 - 环境搭建)
Jmeter(一) - 环境搭建
1.JMeter 介绍 Apache JMeter是100%纯JAVA桌面应用程序，被设计为用于测试客户端/服务端结构的软件(例如web应用程序)。它可以用来测试静态和动态资源的性能，例如：静态文件，Java Servlet,CGI Scripts,Java Object,数据库和FTP服务器…...
OpenCV CUDA 模块特征检测与描述------在GPU上执行特征描述符匹配的类cv::cuda::DescriptorMatcher
操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述 cv::cuda::DescriptorMatcher 是 OpenCV 的 CUDA 模块中用于在 GPU 上执行特征描述符匹配的类。它允许你利用 NVIDIA GPU 的并行计算能力来加速特…...
idea如何让文件夹分层显示，而不是圆点分割
网上说是点击小齿轮的都是过时了，对于新版idea不适用，直接上图 1、如图 2、如图 注意也是去掉Compact Middle Packages，只不过新版的方式UI和老版本的不一样了...
5：OpenCV—直方图均衡化
直方图均衡 直方图均衡是一种用于增强和调整图像对比度的图像处理技术。它通过重新分配图像的像素值，使得图像的灰度级在整个范围内均匀分布，从而增强图像的视觉效果。 图像的直方图是像素强度分布的图形表示。它提供了像素值集中位置以及是否存在异常偏…...
内存分页法
现在有个场景，页面需要分页处理，但是后端在查询完数据库后又会进行筛选，就会导致后端的查询数目跟请求的每页条数是不一样。 解决方案：内存分页法 在内存筛选后手动实现分页逻辑，保证返回数量与请求的 pageSize 一致…...
深入解析FramePack：高效视频帧打包技术原理与实践
摘要 本文深入探讨FramePack技术在视频处理领域的核心原理，解析其在不同场景下的应用优势，并通过OpenCV代码示例演示具体实现方法，为开发者提供可落地的技术解决方案。 目录 1. FramePack技术背景 2. 核心工作原理剖析 3. 典型应用场景 …...
)
【EI会议火热征稿中】第二届云计算与大数据国际学术会议（ICCBD 2025)
# ACM独立出版 | EI检索稳定、往届会后4个半月完成EI检索 # 热门征稿主题：大数据、5G/6G、物联网、云计算 # 早投稿早送审早录用！ 重要信息 大会官网：www.iccbd.net 会议主页：【ACM独立出版|EI稳定】第二届云计算与大数据国际…...
对未来软件的看法
有了大模型之后，TypeScript这样增强型javascript语言可能更方便AI来调试。未来的应用会越来越广泛。node.js vue.js会越来越流行。因为方便AI调试，处理错误。 未来，随着 AI 编程工具对 TypeScript 的深度支持（如自动类型推导、错误…...
新兴技术与安全挑战
7.1 云原生安全（K8s安全、Serverless防护） 核心风险与攻击面 Kubernetes配置错误： 风险：默认开放Dashboard未授权访问（如kubectl proxy未鉴权）。防御：启用RBAC，限制ServiceAccount权限。Serverless函数注入： 漏洞代码（AWS Lambda）：def lambda_handler(event, cont…...
Prompt Tuning：轻量级大模型微调全攻略
Prompt Tuning（提示调优）步骤金额流程 传统的 Prompt Tuning（提示调优） 是一种轻量级的大模型微调技术，核心是通过优化连续的提示向量（而非模型参数）来适配特定任务。 一、核心步骤概述 准备任务与数据 明确任务类型（如分类、问答等），准备输入文本和目标标签。加载…...
centos7安装mysql8.0
yum install -y mysql-community-server --nogpgcheckcentos7.9安装mysql8.0 在 CentOS 7.9 上安装 MySQL 8.0，你可以通过多种方式实现，但最推荐的方法是使用 MySQL 官方提供的 yum 仓库。这样可以确保安装的 MySQL 版本是最新的，并且易于管理…...
ZooKeeper 原理解析及优劣比较
大家好，这里是架构资源栈！点击上方关注，添加“星标”，一起学习大厂前沿架构！ 引言 在分布式系统中，服务注册、配置管理、分布式锁、选举等场景都需要一个高可用、一致性强的协调服务。Apache ZooKeeper 凭…...
OD 算法题 B卷 【需要打开多少监视器】
文章目录 需要打开多少监视器 需要打开多少监视器 某长方形停车场，每个车位上方都有对应监控器，在当前车位和前后左右四个方向任意一个车位范围停车时，监控器才需要打开。给出某一时刻停车场的停车分布，统计最少需要打开多少个监…...
鸿蒙路由参数传递
页面test.ets 代码如下： import router from ohos.router Entry Component struct Test {State message: string Hello WorldState username: string huState password: string 1build() {Row() {Column() {Text(this.message).fontSize(50).fontWeight(FontWe…...
课程与考核
6.1 课程讲解与实战考核 6.1.1 SQL注入篇考核 考核目标：通过手动注入与工具结合，获取目标数据库敏感信息。 题目示例： 目标URL：http://vuln-site.com/product?id1 要求： 判断注入类型（联合查询/报错注…...
CNN、RNN、Transformer对于长距离依赖的捕捉能力分析
卷积网络CNN主要依靠深度来捕捉长距离依赖。但这个过程太间接了，因为信息在网络中实际传播了太多层。究竟哪些信息被保留，哪些被丢弃了，弄不清楚。从实践经验来看，卷积网络捕捉长依赖的能力非常弱。这也是为什么在大多数需要长依赖…...
封装POD与PinMap文件总结学习-20250516
基本概念 芯片封装外形图（POD，Package Outline Drawing），详细描述了芯片的物理尺寸、引脚布局和封装类型等信息； Pin Map是芯片封装的一个重要概念。它是一张详细描述芯片封装外形上各个引脚（Pinÿ…...
Qt项目开发中所遇
讲述下面代码所表示的含义： QWidget widget_19 new QWidget(); QVBoxLayout *touchAreaLayout new QVBoxLayout(widget_19);QWidget *buttonArea new QWidget(widget_19); 1、新建一个名为widget_19的QWidget，将给其应用垂直管路布局。 2、新建一个…...
ubuntu chrome无法使用搜狗拼音输入法，无法输入中文
安装好搜狗输入法后用了很久，突然有一天点击chrome自动升级后就没法用了，在别的软件都能用，还以为是配置问题，就在网上搜了好一阵子才找到解决方案，各种找问题，最后发现是需要安装fcitx5-frontend-gtk4&…...
数据结构与算法分析实验14 实现基本排序算法
实现基本排序算法 1. 常用的排序算法简介2. 上机要求3. 上机环境4.程序清单(写明运行结果及结果分析)4.1 程序清单4.1.1 头文件 sort.h 内容如下：4.1.2 实现文件 sort.cpp 内容如下：4.1.3 源文件 main.cpp 内容如下： 4.2 实现展效果示 5.上机…...
uni-app 中使用 mumu模拟器 进行调试和运行详细教程
一、下载mumu模拟器 二、复制安装路径暴保留 在文件夹中打开 三、配置全局adb命令 adb为Android Debug Bridge，就是起到调试桥的作用 打开shell文件夹、里面有一个adb.exe 将当前文件夹地址复制一下，即‘D:\Program Files\Netease\MuMu Player 12\sh…...