CSES-1687 Company Queries I(倍增法)

ops/2024/12/28 14:15:23/

题目传送门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.ppmy.cn/ops/145672.html

相关文章

基于YOLOv5的智能水域监测系统:从目标检测到自动报告生成

随着人工智能技术的迅猛发展&#xff0c;机器视觉在各行各业中得到了广泛的应用&#xff0c;尤其是在安防、农业、环境监测等领域。今天&#xff0c;我们将探索一个结合了YOLOv5目标检测模型和PyQt5界面的智能水域监测系统&#xff0c;它不仅能精准地识别水域中的异常情况&…

[微服务]elasticsearc客服端操作

客户端初始化 Elasticsearch目前最新版本是8.0&#xff0c;其java客户端有很大变化。不过大多数企业使用的还是8以下版本&#xff0c;所以我们选择使用早期的lavaRestClient客户端来学习。 官方文档地址: Elasticsearch Clients | Elastic 在elasticsearch提供的API中&#x…

SpringBoot集成Flowable

一、工作流介绍 1、概念 通过计算机对业务流程的自动化管理。工作流是建立在业务流程的基础上&#xff0c;一个软件的系统核心根本上还是系统的业务流程&#xff0c;工作流只是协助进行业务流程管理。 解决的是&#xff1a;在多个参与者之间按照某种预定义的规则自动进行传递…

如何结合PCA、t-SNE/UMAP与聚类算法进行高维数据分析?

如何结合PCA、t-SNE/UMAP与聚类算法进行高维数据分析&#xff1f; 在处理高维数据时&#xff0c;如何有效地降维并从中提取有价值的信息&#xff0c;一直是数据分析领域中的一个重要问题。我们常常会面临这样一种情况&#xff1a;数据的特征维度过高&#xff0c;传统的聚类算法…

StarRocks 生产部署一套集群,存储空间如何规划?

背景&#xff1a;StarRocks 3.2&#xff0c;存储一体 使用场景&#xff1a;多分析、小查询多单但不高、数据量几百T FE 存储 由于 FE 节点仅在其存储中维护 StarRocks 的元数据&#xff0c;因此在大多数场景下&#xff0c;每个 FE 节点只需要 100 GB 的 HDD 存储&#xff0c…

【AIGC篇】AIGC 引擎:点燃创作自动化的未来之火

&#xff1a;羑悻的小杀马特.-CSDN博客 未来都是惊喜。你生来本应为高山。并非草芥。 引言&#xff1a; 在当今数字化的时代&#xff0c;人工智能生成内容&#xff08;AIGC&#xff09;正以一种前所未有的力量改变着我们的创作领域。它就像一个神秘而强大的魔法师&#xff0c;…

[论文笔记] 从生成到评估:LLM-as-a-judge 的机遇与挑战

https://arxiv.org/pdf/2411.16594 1. LLM-as-a-judge 的引入 传统的评估方法(如 BLEU 和 ROUGE)在处理生成内容的有用性、无害性等细腻属性时表现不足。随着大语言模型(LLM)的发展,提出了 “LLM-as-a-judge”(LLM 作为评估者)的新范式,用于对任务进行评分、排序或选择…

QT 控件定义为智能指针引发的bug

问题描述&#xff1a; std::unique_ptr<QStackedLayout> m_stacked_layout; 如上为定义&#xff1b; 调用&#xff1a; Line13ABClient::Line13ABClient(QWidget *parent) : BaseWidget(parent) { // 成员变量初始化 m_get_ready false; m_tittle_wnd…