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

2023NOIP A层联测27 A.kotori

2023NOIP A层联测27 A.kotori

文章目录

  • 2023NOIP A层联测27 A.kotori
    • 题目大意
    • 思路
    • code

题目大意

琴里的飞船中有 n n n 个人,其中有 n − 1 n - 1 n1 个通道,所以飞船的内部是一个树形结构。每个人从 1 − n 1-n 1n 编号,编号越小代表这个人的投票经验最丰富。

每个人有一个投票装置,初始都没有启动。现在琴里希望她的飞船支持 q q q 次操作,每次操作是以下两种行动之一:

  1. 把第 x x x 个人的投票装置启动。
  2. 由于每个人都想向经验最丰富的人咨询决策,但又不想绕路地去往一个装置前投票,所以还需要快速查询第 x x x 个人到任意一个投票装置的简单路径上的编号最小的人。

n , q ≤ 1 0 6 n , q \le 10^6 n,q106

思路

我们以第一个激活的点为根。

那么询问点 x x x 的答案就是:点 x x x 到根的最小值或者所有已激活的点到根的最小值。

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++) 
using namespace std;
const int N = 1e6 + 5;
int flg[N] , sz[N] , hd[N] , cnt , dis[N];
struct E {int to , nt;
} e[N << 1];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
void dfs1 (int x , int fa) {sz[x] = flg[x];int max1 = 0 , y;for (int i = hd[x] ; i ; i = e[i].nt) {y = e[i].to;if (y == fa) continue;dfs1 (y , x);dis[x] += dis[y] + sz[y];sz[x] += sz[y];}
}
int main () {int u , v;scanf ("%d" , &n);fu (i , 1 , n) scanf ("%1d" , &flg[i]);fu (i , 1 , n - 1) {scanf ("%d%d" , &u , &v);add (u , v) , add (v , u);}dfs1 (1 , 0);
}

相关文章:

2023NOIP A层联测27 A.kotori

2023NOIP A层联测27 A.kotori 文章目录 2023NOIP A层联测27 A.kotori题目大意思路code 题目大意 琴里的飞船中有 n n n 个人&#xff0c;其中有 n − 1 n - 1 n−1 个通道&#xff0c;所以飞船的内部是一个树形结构。每个人从 1 − n 1-n 1−n 编号&#xff0c;编号越小代表…...

循环生成el-descriptions-item

0 后端返回数据格式 {"msg": "操作成功","code": 200,"data": {"id": 42,"contactInfo": [{"contactPerson": "张三","contactPhone": "13688888888"},{"contactP…...

【原创】java+swing+mysql爱心捐赠管理系统设计与实现

摘要&#xff1a; 爱心捐赠管理系统旨在管理和优化捐赠过程&#xff0c;提高效率&#xff0c;增强透明度&#xff0c;并鼓励更多的个人和企业参与公益捐赠&#xff0c;用户可以捐款或者捐物。本系统采用javaswing界面可视化技术&#xff0c;数据库使用mysql。 功能分析&#…...

【小技巧】WPS统计纯汉字(不计标点符号)

【小技巧】WPS统计纯汉字&#xff08;不计标点符号&#xff09; 首先&#xff0c;CtrlF打开查找页面&#xff1a; 选择“高级搜索”&#xff0c;然后勾选“使用通配符”&#xff0c;然后在“查找内容”后面输入&#xff1a;[一-﨩]。注意&#xff1a;一定要带“[]”和“-”且…...

【押题】24考研押题

数二选手来押24数一考研大题 1.大题必有级数。级数出在压轴题&#xff0c;考级数敛散性与数列极限的结合 2.数一倒数第二题65%考画不出图的三重积分&#xff0c;参考19年出法&#xff1b;35%考第一类曲面积分与空间解析几何的结合。大题不会考第二类线面积分 3.概率大题会考参数…...

前端设计模式

前端设计模式 &#x1f3a8; 设计模式是在软件开发中&#xff0c;针对常见问题的解决方案的经验总结。在前端开发中&#xff0c;设计模式可以帮助我们组织和管理代码&#xff0c;提高代码的可维护性和可扩展性。下面列举一些常见的前端设计模式&#xff1a; 1. 单例模式 (Sin…...

Tomcat的类加载器

详情可以参考&#xff1a;https://tomcat.apache.org/tomcat-10.1-doc/class-loader-howto.html 简要说明 Tomcat安装了多种类加载器&#xff0c;以便容器的不同部分、容器中的应用访问能够不同的类和资源。 在Java环境中&#xff0c;类加载器被组织为父-子树的形式。通常情况…...

汽车驾驶智能座舱太阳光模拟器老化试验

一、太阳光模拟器老化试验目的 太阳光模拟器氙光灯老化试验是一种常用的材料老化测试方法&#xff0c;通过模拟自然光照条件下的老化过程&#xff0c;评估材料的耐光性能和耐候性能其主要目的有: 1.评估材料在长时间暴露于自然光照条件下的耐久性能: 2.比较不同材料的耐光性…...

记录一次校园CTF--wp

一.第一题简单nc 这题直接nc 地址端口即可得到flags没有套路 二.第二题pwn:ezstack 这是一题栈溢出题目&#xff0c;查看保护&#xff1a; 没有开启PIE&#xff0c;运行下查看效果&#xff1a; 题目是一个文字购物游戏。 接着扔进IDA中分析&#xff1a; 在主函数中我们找到…...

基于减法平均算法的无人机航迹规划-附代码

基于减法平均算法的无人机航迹规划 文章目录 基于减法平均算法的无人机航迹规划1.减法平均搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用减法平均算法来优化无人机航迹规划。 …...

C语言--每日五道选择题--Day4

第一题 1、如果 x2014 &#xff0c;下面函数的返回值是&#xff08; &#xff09; int fun(unsigned int x) {int n 0;while(x 1){n;x x | (x 1);}return n; } A: 20 B: 21 C: 23 D: 25 答案及解析 C 这个函数的作用是对整型中0的个数进行统计 x x | (x1) 的作用是每次…...

OpenCV图片验证码识别与滑块验证码识别

目录 图片验证码识别&#xff1a; 一、百度OCR文字识别云服务 二、维普网获取图片验证码 三、维普网opencvocr识别验证码 四、维普网selenium登录并获取数据 滑块验证码&#xff1a; 五、猎聘网获取滑块验证码 六、猎聘网opencv计算滑动距离 七、猎聘网selenium模拟滑…...

网络安全深入学习第八课——代理与端口转发

文章目录 一、什么是代理二、正向代理三、反向代理四、正向和反向代理模拟复现 一、什么是代理 代理服务器英文全称是Proxy Server&#xff0c;其功能就是代理网络用户去取得网络信息。 形象的说&#xff1a;它是网络信息的中转站。在一般情况下&#xff0c;我们使用网络浏览…...

11月7日,每日信息差

今天是2023年11月07日&#xff0c;以下是为您准备的17条信息差 第一、五粮液否认内部讨论提价传闻 第二、雷军证实小米14销量已超百万台 第三、支付宝生活号全面开放UGC入口。据了解&#xff0c;今年以来&#xff0c;支付宝生活号陆续上线了创作者中心、热点榜单等多个内容产…...

sql异常Encountered unexpected token BINARY

1.出现错误 2023-11-06 10:48:19.604 [http-nio-8091-exec-3] WARN c.b.m.e.p.i.PaginationInnerInterceptor - [autoCountSql,343] - [e322891e-de87-4d98-8456-f6448d3c165e] - optimize this sql to a count sql has exception, sql:"selects.id,s.command,s.catego…...

P1131 [ZJOI2007] 时态同步

Portal. 先找出树上以 S S S 为起点最长的一条链&#xff0c;然后让其他链的长度都和该链对齐即可。 维护每个结点 x x x 的子树最长链 d max ⁡ ( x ) d_{\max}(x) dmax​(x)&#xff0c;则每次 DFS 求出最长链之后调整对齐的代价为 d max ⁡ ( x ) − ( d max ⁡ ( s o …...

springboot(ssm 旅游管理系统 旅游规划平台 Java(codeLW)

springboot(ssm 旅游管理系统 旅游规划平台 Java(code&LW) 开发语言&#xff1a;Java 框架&#xff1a;ssm/springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;mysql 5.7&#xff08;或8.0&#xff…...

C++ 构造函数不能是虚函数的原因

构造函数不能被声明为虚函数的主要原因涉及到对象的创建和初始化过程以及虚函数的工作机制。下面详细解释为什么构造函数不能是虚函数&#xff1a; 1.构造函数的调用顺序&#xff1a; 构造函数用于创建对象&#xff0c;并且对象的构造是在派生类构造函数之前完成的。当你创建…...

【LearnOpenGL基础入门——2】搭建第一个OpenGL窗口

目录 一.配置GLFW 二.配置GLAD 三.第一个OpenGL窗口 3.1 GLFW设置 3.2 GLAD设置 3.3 视口 3.4 输入 3.5渲染 在我们画出出色的效果之前&#xff0c;首先要做的就是创建一个OpenGL上下文(Context)和一个用于显示的窗口。然而&#xff0c;这些操作在每个系统上都是不一样…...

第三章:人工智能深度学习教程-人工智能与机器学习与深度学习之间的区别

人工智能基本上是通过一组规则&#xff08;算法&#xff09;将人类智能融入机器的机制。人工智能是两个词的组合&#xff1a;“人工”是指由人类或非自然物体制造的东西&#xff0c;“智能”是指相应地理解或思考的能力。另一个定义可能是“人工智能基本上是训练机器&#xff0…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...