CSES-1687 Company Queries I(倍增法)

题目传送门icon-default.png?t=O83Ahttps://vjudge.net/problem/CSES-1687#author=GPT_zh

解题思路

其实和倍增法求 LCA 是一样的……

首先设 f(i,j) 表示 i 号点的上面的第 2^j 个祖先是谁。

同倍增法:f(i,j)=f(f(i,j-1),j-1)

然后,题目要求我们向上跳 k 个点。

枚举 j(从大到小,想想为什么),然后每次跳时 k-=2^j

若最后 k\neq 0,那么就跳不完,说明没有,输出 -1.

否则输出答案即可。

代码

这里加了一个常数优化,lg(i) 表示 \log_2^i 的值。

#include<bits/stdc++.h>
using namespace std;int n,q;
vector<int> g[200001];
int f[200001][31];
int lg[200001];
int dep[200001];
void dfs(int x,int fa)
{dep[x]=dep[fa]+1;f[x][0]=fa;for(int i=1;i<=lg[dep[x]];i++){f[x][i]=f[f[x][i-1]][i-1];}for(auto y:g[x]){if(y!=fa){dfs(y,x);}}
}
int solve(int u,int k)
{if(k==0)return u;bool bj=0;for(int i=lg[k];i>=0;i--){if(f[u][i]!=-1&&k-(1<<i)>=0){u=f[u][i];k-=(1<<i);bj=1;}}if(k==0)return u;return -1;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;int x;for(int i=2;i<=n;i++){cin>>x;g[i].push_back(x);g[x].push_back(i);}memset(f,-1,sizeof f);lg[0]=1;for(int i=1;i<=n;i++){lg[i]=lg[i-1]+(1<<lg[i-1]==i);}dfs(1,-1);int y;while(q--){cin>>x>>y;cout<<solve(x,y)<<"\n";}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/496738.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【从零开始入门unity游戏开发之——unity篇01】unity6基础入门开篇——游戏引擎是什么、主流的游戏引擎、为什么选择Unity

文章目录 前言**游戏引擎是什么&#xff1f;****游戏引擎对于我们的意义**1、**降低游戏开发的门槛**2、**提升游戏开发效率** **以前做游戏****现在做游戏****主流的游戏引擎有哪些&#xff1f;**Unity 相比其他游戏引擎的优势&#xff1f;**为什么选择Unity&#xff1f;**Uni…

Apifox 12月更新|接口的测试覆盖情况、测试场景支持修改记录、迭代分支能力升级、自定义项目角色权限、接口可评论

Apifox 新版本上线啦&#xff01;&#xff01;&#xff01; 在快速迭代的开发流程中&#xff0c;接口测试工具的强大功能往往决定了项目的效率和质量。而 Apifox 在 12 月的更新中&#xff0c;再次引领潮流&#xff0c;推出了一系列重磅功能&#xff01;测试覆盖情况分析、场景…

C# GDI+数码管数字控件

调用方法 int zhi 15;private void button1_Click(object sender, EventArgs e){if (zhi > 19){zhi 0;}lcdDisplayControl1.DisplayText zhi.ToString();} 运行效果 控件代码 using System; using System.Collections.Generic; using System.Drawing.Drawing2D; using …

WebRTC服务质量(12)- Pacer机制(04) 向Pacer中插入数据

WebRTC服务质量&#xff08;01&#xff09;- Qos概述 WebRTC服务质量&#xff08;02&#xff09;- RTP协议 WebRTC服务质量&#xff08;03&#xff09;- RTCP协议 WebRTC服务质量&#xff08;04&#xff09;- 重传机制&#xff08;01) RTX NACK概述 WebRTC服务质量&#xff08;…

C#实现调用DLL 套壳读卡程序(桌面程序开发)

背景 正常业务已经支持 读三代卡了&#xff0c;前端调用医保封装好的服务就可以了&#xff0c;但是长护要读卡&#xff0c;就需要去访问万达&#xff0c;他们又搞了一套读卡的动态库&#xff0c;为了能够掉万达的接口&#xff0c;就需要去想办法调用它们提供的动态库方法&…

低代码开发平台排名2024

低代码开发平台在过去几年中迅速崛起&#xff0c;成为企业数字化转型的重要工具。这些平台通过可视化界面和拖放组件&#xff0c;使业务人员和技术人员都能快速构建应用程序&#xff0c;大大缩短了开发周期。以下是一些在2024年值得关注和使用的低代码开发平台。 一、Zoho Cre…

rocketmq-push模式-消费侧重平衡-类流程图分析

1、观察consumer线程 使用arthas分析 MQClientFactoryScheduledThread 定时任务线程 定时任务线程&#xff0c;包含如下任务&#xff1a; 每2分钟更新nameServer列表 每30秒更新topic的路由信息 每30秒检查broker的存活&#xff0c;发送心跳请求 每5秒持久化消费队列的offset…

群落生态学研究进展▌Hmsc包对于群落生态学假说的解读、Hmsc包开展单物种和多物种分析的技术细节及Hmsc包的实际应用

HMSC&#xff08;Hierarchical Species Distribution Models&#xff09;是一种用于预测物种分布的统计模型。它在群落生态学中的应用广泛&#xff0c;可以帮助科学家研究物种在不同环境条件下的分布规律&#xff0c;以及预测物种在未来环境变化下的潜在分布范围。 举例来说&a…

影视仓最新接口+内置本包方法的研究(2024.12.27)

近日喜欢上了研究影视的本地仓库内置&#xff0c;也做了一个分享到了群里。 内置本地仓库包的好处很明显&#xff0c;当前线路接口都是依赖网络上的代码站存放&#xff0c;如果维护者删除那就GG。 虽然有高手制作了很多本地包&#xff0c;但推送本地包到APP&#xff0c;难倒一片…

教育元宇宙的优势与核心功能解析

随着科技的飞速发展&#xff0c;教育领域正迎来一场前所未有的变革。教育元宇宙作为新兴的教育形态&#xff0c;以其独特的优势和丰富的功能&#xff0c;正在逐步改变我们的学习方式。本文将深入探讨教育元宇宙的优势以及其核心功能&#xff0c;为您揭示这一未来教育的新趋势。…

多个微服务 Mybatis 过程中出现了Invalid bound statement (not found)的特殊问题

针对多个微服务的场景&#xff0c;记录一下这个特殊问题&#xff1a; 如果启动类上用了这个MapperScan注解 在resource 目录下必须建相同的 com.demo.biz.mapper 目录结构&#xff0c;否则会加载不到XML资源文件 。 并且切记是com/demo/biz 这样的格式创建&#xff0c;不要使用…

Java基础知识(四) -- 面向对象(下)

1.类变量和类方法 1.1 类变量背景 有一群小孩在玩堆雪人,不时有新的小孩加入,请问如何知道现在共有多少人在玩? 思路分析: 核心在于如何让变量count被所有对象共享 public class Child {private String name;// 定义静态变量(所有Child对象共享)public static int count 0;p…

Linux系统之stat命令的基本使用

Linux系统之stat命令的基本使用 一、stat命令 介绍二、stat命令帮助2.1 查询帮助信息2.2 stat命令的帮助解释 三、stat命令的基本使用3.1 查询文件信息3.2 查看文件系统状态3.3 使用格式化输出3.4 以简洁形式打印信息 四、注意事项 一、stat命令 介绍 stat 命令用于显示文件或文…

雷池 WAF 搭配阿里云 CDN 使用教程

雷池 WAF&#xff08;Web Application Firewall&#xff09;是一款强大的网络安全防护产品&#xff0c;通过实时流量分析和精准规则拦截&#xff0c;有效抵御各种网络攻击。在部署雷池 WAF 的同时&#xff0c;结合阿里云 CDN&#xff08;内容分发网络&#xff09;可以显著提升网…

蓝桥杯速成教程{三}(adc,i2c,uart)

目录 一、adc 原理图​编辑引脚配置 Adc通道使能配置 实例测试 ​编辑效果显示 案例程序 badc 按键相关函数 测量频率占空比 main 按键的过程 显示界面的过程 二、IIC通信-eeprom 原理图AT24C02 引脚配置 不可用状态&#xff0c;用的软件IIC 官方库移植 At24c02手册 ​编辑…

Semantic Segmentation Editor标注工具

https://github.com/Hitachi-Automotive-And-Industry-Lab/semantic-segmentation-editor https://docs.meteor.com/about/install.html https://v2-docs.meteor.com/install.html 安装指定版本的meteor curl https://install.meteor.com/\?release\2.12 | sh ubuntu18 安…

攻防世界web新手第四题easyphp

<?php highlight_file(__FILE__); $key1 0; $key2 0;$a $_GET[a]; $b $_GET[b];if(isset($a) && intval($a) > 6000000 && strlen($a) < 3){if(isset($b) && 8b184b substr(md5($b),-6,6)){$key1 1;}else{die("Emmm...再想想&quo…

vxe-table 实现跨行按钮同时控制两行的编辑状态

vxe-table 写可编辑表格用起来很爽吧&#xff01;有没有遇到下面这种要用一个跨行按钮&#xff0c;控制两行编辑框是否可编辑的情况。是不是官网的方法不好实现了&#xff1f;那么这个应该怎么实现呢。最近刚好碰到这个问题。说下个人的实现思路。 其实也简单&#xff0c;既然官…

ES 磁盘使用率检查及处理方法

文章目录 1. 检查原因2. 检查方法3. 处理方法3.1 清理数据3.2 再次检查磁盘使用率 1. 检查原因 磁盘使用率在 85%以下&#xff0c;ES 可正常运行&#xff0c;达到 85%及以上会影响 PEIM 数据存储。 在 ES 磁盘分配分片控制策略中&#xff0c;为了保护数据节点的安全&#xff0…

论文解读 | EMNLP2024 一种用于大语言模型版本更新的学习率路径切换训练范式

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入&#xff01; 点击 阅读原文 观看作者讲解回放&#xff01; 作者简介 王志豪&#xff0c;厦门大学博士生 刘诗雨&#xff0c;厦门大学硕士生 内容简介 新数据的不断涌现使版本更新成为大型语言模型&#xff08;LLMs&#xff…