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

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...