当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...