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

(枚举 + 树上倍增)Codeforces Round 900 (Div. 3) G

Problem - G - Codeforces

题意:

思路:

首先,目标值和结点权值是直接联系的,最值不可能直接贪心,一定是考虑去枚举一些东西,依靠这种枚举可以遍历所有的有效情况,思考的方向一定是枚举

如果去直接在链上枚举的话, 复杂度是O(nq),肯定不行

注意到一条路径上的前缀或值不会超过 logV个,因此考虑枚举前缀或值

 

关于每次跳使前缀或值变化的最深的点,我是这样理解的

如果考虑在链上枚举,如果前缀或值不变,那么这样的枚举是无效的,我们直接考虑跳着枚举,只枚举所有有效情况

关于怎么跳其实可以参考树上倍增往上跳的跳法,记录一个数组指向下一个结点,在dfs上维护即可,有点像在树链上DP

Code:

#include <bits/stdc++.h>#define int long longconstexpr int N = 2e5 + 10;std::vector<int> adj[N];int n;
int a[N];
int dep[N];
int f[N][33], s[N][33], lst[N][33];void dfs(int u, int fa) {dep[u] = dep[fa] + 1;f[u][0] = fa;for (int j = 1; j <= 30; j ++) f[u][j] = f[f[u][j - 1]][j - 1];int val = a[u];for (int j = 30; j >= 0; j --) {if (!((val >> j) & 1)) {lst[u][j] = lst[fa][j];s[u][j] = s[fa][j];}else {lst[u][j] = u;s[u][j] = s[fa][j] + 1;}}for (auto v : adj[u]) {if (v == fa) continue;dfs(v, u);}
}
int lca(int u, int v) {if (dep[u] < dep[v]) std::swap(u, v);for (int j = 30; j >= 0; j --) {if (dep[f[u][j]] >= dep[v]) {u = f[u][j];}}if (u == v) return u;for (int j = 30; j >= 0; j --) {if (f[u][j] != f[v][j]) {u = f[u][j];v = f[v][j];}}return f[u][0];
}
int calc(int x, int y, int lca) {int res = 0;for (int j = 0; j <= 30; j ++) {if (s[x][j] + s[y][j] - s[lca][j] - s[f[lca][0]][j]) res ++;}return res;
}
void solve() {std::cin >> n;for (int i = 1; i <= n; i ++) {adj[i].clear();dep[i] = 0;for (int j = 30; j >= 0; j --) {f[i][j] = s[i][j] = lst[i][j] = 0;}}for (int i = 1; i <= n; i ++) std::cin >> a[i];for (int i = 1; i <= n - 1; i ++) {int u, v;std::cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}dfs(1, 0);int q;int ans = 0;std::cin >> q;while(q --) {int x, y;std::cin >> x >> y;int cur = x, val = a[x];ans = 0;while(1) {int nxt = 0, mx = 0;ans = std::max(ans, calc(x, cur, lca(x, cur)) + calc(cur, y, lca(cur, y)));for (int j = 30; j >= 0; j --) {if (!((val >> j) & 1)) {if (dep[lst[cur][j]] >= dep[lca(x, y)]) {if (dep[lst[cur][j]] > mx) {mx = dep[lst[cur][j]];nxt = lst[cur][j];}}}}if (!mx) break;val |= a[nxt];cur = nxt;}cur = y, val = a[y];while(1) {int nxt = 0, mx = 0;ans = std::max(ans, calc(x, cur, lca(x, cur)) + calc(cur, y, lca(cur, y)));for (int j = 30; j >= 0; j --) {if (!((val >> j) & 1)) {if (dep[lst[cur][j]] >= dep[lca(x, y)]) {if (dep[lst[cur][j]] > mx) {mx = dep[lst[cur][j]];nxt = lst[cur][j];}}}}if (!mx) break;val |= a[nxt];cur = nxt;}std::cout << ans << " ";}std::cout << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}

相关文章:

(枚举 + 树上倍增)Codeforces Round 900 (Div. 3) G

Problem - G - Codeforces 题意&#xff1a; 思路&#xff1a; 首先&#xff0c;目标值和结点权值是直接联系的&#xff0c;最值不可能直接贪心&#xff0c;一定是考虑去枚举一些东西&#xff0c;依靠这种枚举可以遍历所有的有效情况&#xff0c;思考的方向一定是枚举 如果去…...

websocket逆向【python实现websocket拦截】

python实现websocket拦截 前言一、拦截的优缺点优点:缺点:二、实现方法1.环境配置2.代码三、总结前言 开发者工具F12,筛选ws后,websocket的消息是这样显示的,如何获取这里面的消息呢? 以下是本篇文章正文内容 一、拦截的优缺点 主要讲解一下websocket拦截的实现,现在…...

软件测试自动化的成本效益分析

随着软件测试技术的发展&#xff0c;人们已经从最初的手工测试转变为手工和自动化技术相结合的测试方法。目前&#xff0c;人们更多的是关心自动化测试框架、自动化测试工具以及脚本研究等技术方面&#xff0c;而在软件自动化测试方案的效益分析方面涉及较少。 软件测试的目的是…...

【Java】状态修饰符 final static

目录 final 修饰我们的成员方法、成员变量、类 示例代码&#xff1a; final 修饰的局部变量 示例代码&#xff1a; static 示例代码&#xff1a; static 访问特点&#xff1a; 示例代码&#xff1a; static关键字的用途 示例代码&#xff1a; static 修饰常量 示例…...

笔试编程ACM模式JS(V8)、JS(Node)框架、输入输出初始化处理、常用方法、技巧

目录 考试注意事项 先审完题意&#xff0c;再动手 在本地编辑器&#xff08;有提示&#xff09; 简单题515min 通过率0%&#xff0c;有额外log 常见输入处理 str-> num arr&#xff1a;line.split( ).map(val>Number(val)) 初始化数组 new Array(length).fill(v…...

learn掩码张量

目录 1、什么是掩码张量 2、掩码张量的作用 3、代码演示 &#xff08;1&#xff09;、定义一个上三角矩阵&#xff0c;k0或者 k默认为 0 &#xff08;2&#xff09;、k1 &#xff08;3&#xff09;、k-1 4、掩码张量代码实现 &#xff08;1&#xff09;、输出效果 &…...

激活函数介绍

介绍 神经网络当中的激活函数用来提升网络的非线性&#xff0c;以增强网络的表征能力。它有这样几个特点&#xff1a;有界&#xff0c;必须为非常数&#xff0c;单调递增且连续可求导。我们常用的有sigmoid或者tanh&#xff0c;但我们都知道这两个都存在一定的缺点&#xff0c…...

docker方式启动一个java项目-Nginx本地有代码,并配置反向代理

文章目录 案例导入说明1.安装MySQL1.1.准备目录1.2.运行命令1.3.修改配置1.4.重启 2.导入SQL3.导入Demo工程3.1.分页查询商品&#xff08;仔细看代码&#xff0c;很多新的MP编程技巧&#xff09;3.2.新增商品3.3.修改商品3.4.修改库存3.5.删除商品3.6.根据id查询商品3.7.根据id…...

前端和后端是Web开发选哪个好?

前端和后端是Web开发中的两个不同的领域&#xff0c;哪一种更适合学习&#xff1f;前景更广呢&#xff1f; 一、引言 Web前端开发就像装饰房间的小瓦匠&#xff0c;勤勤恳恳&#xff0c;仔仔细细&#xff0c;粉饰墙壁&#xff0c;妆点家具。会 HTML,CSS&#xff0c;懂点 JS。…...

HTTP协议,请求响应

、概述 二、HTTP请求协议 三、HTTP响应协议 四、请求数据 1.简单实体参数 RequestMapping("/simpleParam")public String simpleParam(RequestParam(name "name" ,required false ) String username, Integer age){System.out.println (username "…...

idea配置文件属性提示消息解决方案

在项目文件路径下找到你没有属性提示消息的文件 选中&#xff0c;ok即可 如果遇到ok无法确认的情况&#xff1a; 在下图所示位置填写配置文件名称即可...

EdgeView 4 for Mac:重新定义您的图像查看体验

您是否厌倦了那些功能繁杂、操作复杂的图像查看器&#xff1f;您是否渴望一款简单、快速且高效的工具&#xff0c;以便更轻松地浏览和管理您的图像库&#xff1f;如果答案是肯定的&#xff0c;那么EdgeView 4 for Mac将是您的理想之选&#xff01; EdgeView 4是一款专为Mac用户…...

流程自动化(RPA)的好处有哪些?

流程自动化&#xff08;RPA&#xff09;是一种通过软件机器人实现业务流程自动化的技术。它可以模拟人类在计算机上执行的操作&#xff0c;从而自动化重复性、繁琐的任务&#xff0c;提高工作效率和准确性。流程自动化&#xff08;RPA&#xff09;的好处很多&#xff0c;下面我…...

医学影像系统【简称PACS】源码

PACS(Picture Archiving and Comuniations Systems)即PACS&#xff0c;图像存储与传输系统&#xff0c;是应用于医院中管理医疗设备如CT&#xff0c;MR等产生的医学图像的信息系统。目标是支持在医院内部所有关于图像的活动&#xff0c;集成了医疗设备&#xff0c;图像存储和分…...

大家都在用哪些敏捷开发项目管理软件?

敏捷开发是一种以人为核心、迭代、循序渐进的开发方法。 敏捷开发的特点是高度灵活性和适应性、迭代式开发。 敏捷开发方法强调快速响应变化&#xff0c;因此它具有高度的灵活性和适应性。开发团队可以根据客户需求和市场变化快速调整开发计划和产品功能&#xff0c;以确保产品…...

python机器学习基础教程01-环境搭建

书籍源代码 github上源代码 https://github.com/amueller/introduction_to_ml_with_python 安装anaconda虚拟环境 创建虚拟环境 conda create -p E:\Python\envs\mlstupy35 python3.5 # 激活环境 conda activate E:\Python\envs\mlstupy35 # 创建学习目录 cd G:\Python\ml…...

TinyWebServer学习笔记-Config

为了弄清楚具体的业务逻辑&#xff0c;我们直接从主函数开始看源代码&#xff1a; #include "config.h"int main(int argc, char *argv[]) {//需要修改的数据库信息,登录名,密码,库名string user "root";string passwd "root";string databas…...

数据结构与算法--算法

这里写目录标题 线性表顺序表链表插入删除算法 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 线性表 顺序表 链表 插入删除算法 步骤 1.通过循环到达指定位置的前一个位置 2.新建…...

JVM:如何通俗的理解并发的可达性分析

并发的可达性分析 前面在介绍对象是否已死那一节有说到可达性分析算法&#xff0c;它理论上是要求全过程都基于一个能保障一致性的快照&#xff08;类比 MySQL 的MVCC&#xff09;中才能够进行分析&#xff0c;也就意味着必须全程冻结用户线程的运行&#xff08;STW&#xff0…...

传统机器学习聚类算法——总集篇

工作需要&#xff0c;涉及到一些聚类算法相关的知识。工作中需要综合考虑数据量、算法效果、性能之间的平衡&#xff0c;所以开启新的篇章——机器学习聚类算法篇。 传统机器学习中聚类算法主要分为以下几类&#xff1a; 1. 层次聚类算法 层次聚类算法是一种无监督学习算法&am…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...