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

5560.树的直径

蛮不错的一道题目,你要利用树的性质分析出,你只需要维护上一次的树的直径的两个端点就好了

#include<iostream>using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 6e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}int n,q,m;// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }int dep[N];
int fa[N][22];int lca(int a,int b){if(dep[a]<dep[b])swap(a,b);for(int i=20;i>=0;--i)if(dep[fa[a][i]]>=dep[b])a = fa[a][i];if(a==b)return a;for(int i=20;i>=0;--i)if(fa[a][i]!=fa[b][i])a = fa[a][i],b =fa[b][i];return fa[a][0];}int dist(int a,int b){return dep[a]+dep[b]-2*dep[lca(a,b)];
}void solve()
{cin>>n;dep[2] = dep[3] = dep[4] = 2;dep[1] = 1;fa[1][0] = 0;fa[2][0] = fa[3][0] = fa[4][0] = 1;int tem = 4;int A = 2,B = 3;while(n--){int a;cin>>a;int b = ++tem,c = ++tem;fa[b][0] = a,fa[c][0] = a;dep[b] = dep[a]+1,dep[c] = dep[a]+1;for(int i=1;i<=20;i++)fa[b][i] = fa[fa[b][i-1]][i-1] ;for(int i=1;i<=20;i++)fa[c][i] = fa[fa[c][i-1]][i-1] ;int dista = dist(b,A),distb = dist(b,B);int dists = dist(A,B);//cout<<A<<" "<<B<<" "<<b<<" "<<dista<<" "<<distb<<" "<<dists<<"\n";if(dista<=dists&&distb<=dists){cout<<dists<<"\n";continue;}if(dista>dists&&dista>=distb){B=b;cout<<dista<<"\n";continue;}if(distb>dists){A=b;cout<<distb<<"\n";continue;}}}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin>>_;_ = 1;while(_--)solve();return 0;
}

相关文章:

5560.树的直径

蛮不错的一道题目&#xff0c;你要利用树的性质分析出&#xff0c;你只需要维护上一次的树的直径的两个端点就好了 #include<iostream>using namespace std; using ll long long; using pii pair<int,int>; const int N 6e510; const int inf 0x3f3f3f3f; cons…...

Decoupled Multimodal Distilling for Emotion Recognition 论文阅读

Decoupled Multimodal Distilling for Emotion Recognition 论文阅读 Abstract1. Introduction2. Related Works2.1. Multimodal emotion recognition2.2. Knowledge distillation3. The Proposed Method3.1. Multimodal feature decoupling3.2. GD with Decoupled Multimodal …...

【css】使用display:inline-block后,元素间存在4px的间隔

问题&#xff1a;在本地项目中使用【display: inline-block】&#xff0c;元素间存在4px间隔。打包后发布到外网又不存在这个问题了。 归根结底这是一个西文排版的问题&#xff0c;英文有空格作为词分界&#xff0c;而中文则没有。 此时的元素具有文本属性&#xff0c;只要标签…...

代码执行漏洞

原理&#xff1a;没有对接口输入的内容进行严格的判断 造成攻击者精心构造的代码非法执行 当应用在调用一些能将字符转化为代码的函数(如PHP中的eval)时&#xff0c;没有考虑用户是否能控 制这个字符串&#xff0c;这就会造成代码执行漏洞。 相 关 函 数 &#xff1a; PHP&…...

SQLServer2022安装

首先从官网上下载2022版本SQL Server 下载 | Microsoft 选择此把呢不能运行&#xff0c;适合我们在学习阶段使用。 同时网页往下滑动&#xff0c;下载SSMS 下载后的文件 注意&#xff1a;在运行时最好获取管理员权限运行&#xff0c;第一次在安装时未获取管理员权限最终…...

vue2 配置@指向src

使用的是vue cli创建的项目。 1.安装 path 如果在 Node.js 环境中运行代码&#xff0c;path 模块默认是可用的&#xff0c;则不需要单独安装&#xff0c;否则输入下面命令安装path npm i path -S 2.找到vue.config.js文件&#xff1a; const { defineConfig } require(vue/…...

用友U9 存在PatchFile.asmx接口任意文件上传漏洞

声明&#xff1a; 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 简介 用友U9是由中国用友软件股份有限公司开发的一款企业…...

如何卸载干净 IDEA(图文讲解)

更新时间 2022-12-20 11:一则或许对你有用的小广告 星球 内第一个项目&#xff1a;全栈前后端分离博客项目&#xff0c;演示地址&#xff1a;Weblog 前后端分离博客, 1.0 版本已经更新完毕&#xff0c;正在更新 2.0 版本。采用技术栈 Spring Boot Mybatis Plus Vue 3.x Vit…...

自动化运维(十)Ansible 之进程管理模块

Ansible的进程管理模块提供了一种强大而灵活的方式来管理和操作各种进程管理器和服务。无论你使用的是Supervisor、Systemd、传统的init脚本还是Runit,这些模块都可以帮助你轻松地管理服务的生命周期。通过合理地使用这些模块,你可以实现服务的自动化管理,提高系统的可靠性和稳…...

【leetcode279】完全平方数,动态规划解法

原问题&#xff1a;给定一个非负整数n&#xff0c;如果把它视作一些完全平方数的和&#xff0c;那么最少需要多少个完全平方数&#xff1f; 这次学习到一个热心网友的解法&#xff1a;把问题转化兑换零钱问题&#xff0c;然后使用动态规划求解。 比如&#xff0c;给定 n12, 那…...

Java 元素排序(数组、List 集合)

数组元素排序 升序 int[] array {3, 1, 4, 5}; Arrays.sort(array);// 升序排序 System.out.println(Arrays.toString(array)); //输出&#xff1a;[1, 3, 4, 5]降序 可以先将数组元素存入 List 集合&#xff0c;然后集合元素逆序&#xff0c;最后将集合元素写回原数组。&a…...

使用vite创建一个react18项目

一、vite是什么&#xff1f; vite 是一种新型前端构建工具&#xff0c;能够显著提升前端开发体验。它主要由两部分组成&#xff1a; 一个开发服务器&#xff0c;它基于原生 ES 模块提供了丰富的内建功能&#xff0c;如速度快到惊人的模块热更新&#xff08;HMR&#xff09;。 …...

子集(迭代)(leetcode 78)

核心逻辑&#xff1a; 根据子数组包含的元素个数迭代&#xff1a; 现有子集的基础上通过添加这个新元素来翻倍子集的数量 f(n)2f(n−1) vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;int i,j,k;ans.p…...

汽车疲劳测试试验平台技术要求(北重厂家)

汽车疲劳测试试验平台技术要求通常包括以下几个方面&#xff1a; 车辆加载能力&#xff1a;测试平台需要具备足够的承载能力&#xff0c;能够同时测试多种车型和不同重量的车辆。 动力系统&#xff1a;测试平台需要具备稳定可靠的动力系统&#xff0c;能够提供足够的力和速度来…...

Redis -- 缓存雪崩问题

缓存雪崩是指在同一时段大量的缓存key同时失效或者Redis服务宕机&#xff0c;导致大量请求到达数据库&#xff0c;带来巨大压力。 可能原因 : 同一时间大量的key到期 ; 解决方案&#xff1a; 给不同的Key的TTL添加随机值 利用Redis集群提高服务的可用性 给缓存业务添加降…...

【ARM 嵌入式 C 文件操作系列 20 -- 文件删除函数 remove 详细介绍】

请阅读【嵌入式开发学习必备专栏 】 文章目录 文件删除函数 remove 文件删除函数 remove 在 C 语言中&#xff0c; 可以使用 remove 函数来删除一个文件&#xff0c;但在删除之前 可能想确认该文件是否存在。 可以使用 stat 函数来检查文件是否存在。 以下是如何实现这个功能…...

LeetCode刷题之31.下一个排列

文章目录 1. 题目2.分析3.解答3.1 先排序&#xff0c;后交换3.2 先交换&#xff0c;后排序 1. 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3…...

【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(九)- 向量定点算术指令

1. 引言 以下是《riscv-v-spec-1.0.pdf》文档的关键内容&#xff1a; 这是一份关于向量扩展的详细技术文档&#xff0c;内容覆盖了向量指令集的多个关键方面&#xff0c;如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量…...

【Java网络编程】IP网络协议与TCP、UDP网络传输层协议

1.1、IP协议 当应用层的数据被封装后&#xff0c;想要将数据在网络上传输&#xff0c;数据究竟要被发往何处&#xff0c;又该如何精准的在网络上定位目标机器&#xff0c;此时起到关键作用的就是“IP协议”。IP协议的作用在于把各种数据包准确无误的传递给目标方&#xff0c;其…...

C# 分布式自增ID算法snowflake(雪花算法)

文章目录 1. 概述2. 结构3. 代码3.1 IdWorker.cs3.2 IdWorkerTest.cs (测试) 1. 概述 分布式系统中&#xff0c;有一些需要使用全局唯一ID的场景&#xff0c;这种时候为了防止ID冲突可以使用36位的UUID&#xff0c;但是UUID有一些缺点&#xff0c;首先他相对比较长&#xff0c…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...