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

NC204871 求和

链接

思路:

        对于一个子树来说,子树的节点就包括在整颗树的dfs序中子树根节点出现的前后之间,所以我们先进行一次dfs,用b数组的0表示区间左端点,1表示区间右端点,同时用a数组来标记dfs序中的值。处理完dfs序后,我们就用dfs序列来建树,若要查询或修改一个子树,则区间就是b0到b1,由于在dfs序列中每个数都会出现两次,所以查询的结果是正确答案的两倍,我们只需要最后除以2即可。

 代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
//#define int long long
//const ll P=2281701377;
const ll P=998244353;
const int mod=1e9+7;int n,m,k,a[N],cnt,b[N][2],va[N];
vector<int> v[N];
ll tree[N*4];
void dfs(int x,int f){b[x][0]=++cnt;a[cnt]=x;for(auto y:v[x]){if(y==f) continue;dfs(y,x);} b[x][1]=++cnt;a[cnt]=x;
}
void build(int p,int l,int r){if(l==r){tree[p]=va[a[l]];return;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);tree[p]=tree[p<<1]+tree[p<<1|1];
}
void modify(int p,int l,int r,int a,int x){if(l==r&&l==a){tree[p]+=x;return;}int mid=(l+r)>>1;if(a<=mid) modify(p<<1,l,mid,a,x);else modify(p<<1|1,mid+1,r,a,x);tree[p]=tree[p<<1]+tree[p<<1|1];
}
ll query(int p,int l,int r,int x,int y){if(l>=x&&r<=y){return tree[p];}int mid=(l+r)>>1;ll res=0;if(x<=mid) res+=query(p<<1,l,mid,x,y);if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);tree[p]=tree[p<<1]+tree[p<<1|1];return res;
}
void solve(){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>va[i];}for(int i=1;i<n;i++){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}dfs(k,0);build(1,1,cnt);while(m--){int f,a;cin>>f>>a;if(f==1){int x;cin>>x;modify(1,1,cnt,b[a][0],x);modify(1,1,cnt,b[a][1],x);}else{cout<<query(1,1,cnt,b[a][0],b[a][1])/2<<endl;}}}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}}

相关文章:

NC204871 求和

链接 思路&#xff1a; 对于一个子树来说&#xff0c;子树的节点就包括在整颗树的dfs序中子树根节点出现的前后之间&#xff0c;所以我们先进行一次dfs&#xff0c;用b数组的0表示区间左端点&#xff0c;1表示区间右端点&#xff0c;同时用a数组来标记dfs序中的值。处理完dfs序…...

git克隆代码warning: could not find UI helper ‘git-credential-manager-ui‘

git克隆代码warning: could not find UI helper ‘git-credential-manager-ui’ 方案 git config --global --unset credential.helpergit-credential-manager configure...

Generator 是怎么样使用的以及各个阶段的变化如何

Generators 是 JavaScript 中一种特殊类型的函数&#xff0c;可以在执行过程中暂停&#xff0c;并且在需要时恢复执行。它们是通过 function* 关键字来定义的。Generator 函数返回的是一个迭代器对象&#xff0c;通过调用该迭代器对象的 next() 方法来控制函数的执行。在调用 n…...

一文了解Java中 Vector、ArrayList、LinkedList 之间的区别

目录 1. 数据结构 Vector 和 ArrayList LinkedList 2. 线程安全 Vector ArrayList 和 LinkedList 3. 性能 插入和删除操作 随机访问 4. 内存使用 ArrayList 和 Vector LinkedList 5. 迭代器行为 ArrayList 和 Vector LinkedList 6. 扩展策略 ArrayList Vecto…...

【论文复现|智能算法改进】基于自适应动态鲸鱼优化算法的路径规划研究

目录 1.算法原理2.改进点3.结果展示4.参考文献5.代码获取 1.算法原理 SCI二区|鲸鱼优化算法&#xff08;WOA&#xff09;原理及实现【附完整Matlab代码】 2.改进点 非线性收敛因子 WOA 主要通过控制系数向量 A 来决定鲸鱼是搜索猎物还是捕获猎物&#xff0c;即系数向量 A 可…...

【Win测试】窗口捕获的学习笔记

2 辨析笔记 2.1 mss&#xff1a;捕获屏幕可见区域&#xff0c;不适合捕获后台应用 Claude-3.5-Sonnet: MSS库可以用来捕获屏幕上可见的内容&#xff1b;然而&#xff0c;如果游戏窗口被其他窗口完全遮挡或最小化&#xff0c;MSS将无法捕获到被遮挡的游戏窗口内容&#xff0c;而…...

PostgreSQL的学习心得和知识总结(一百四十七)|深入理解PostgreSQL数据库之transaction chain的使用和实现

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《PostgreSQL数据库内核分析》 2、参考书籍&#xff1a;《数据库事务处理的艺术&#xff1a;事务管理与并发控制》 3、PostgreSQL数据库仓库…...

宝塔linux网站迁移步骤

网站迁移到新服务器步骤 1.宝塔网站迁移&#xff0c;有个一键迁移工具&#xff0c;参考官网 宝塔一键迁移API版本 3.0版本教程 - Linux面板 - 宝塔面板论坛 (bt.cn)2 2.修改域名解析为新ip 3.如果网站没有域名&#xff0c;而是用ip访问的&#xff0c;则新宝塔数据库的wp_o…...

电路笔记(三极管器件): MOSFETIGBT

MOSFET vs IGBT MOSFET主要用于低电压和功率系统&#xff0c;而IGBT更适合高电压和功率系统。 1. MOSFET&#xff08;金属氧化物半导体场效应晶体管&#xff09; 优势&#xff1a; 高开关速度和响应速度&#xff0c;适合高频应用。&#xff08;IGBT不适合高频应用&#xff0c…...

Docker 镜像导出和导入

docker 镜像导出 # 导出 docker 镜像到本地文件 docker save -o [输出文件名.tar] [镜像名称[:标签]] # 示例 docker save -o minio.tar minio/minio:latest-o 或 --output&#xff1a;指定导出文件的路径和名称[镜像名称[:标签]]&#xff1a;导出镜像名称以及可选的标签 dock…...

QueryClientProvider is not defined

QueryClientProvider is not defined 运行一个svelte的项目&#xff0c;报错如上&#xff0c;前后查找解决不了&#xff0c;然后没办法&#xff0c; 本来是用yarn 安装的依赖&#xff0c;改用npm install&#xff0c;再次运行就成功了...

HTTPS是什么?原理是什么?用公钥加密为什么不能用公钥解密?

HTTPS&#xff08;HyperText Transfer Protocol Secure&#xff09;是HTTP的安全版本&#xff0c;它通过在HTTP协议之上加入SSL/TLS协议来实现数据加密传输&#xff0c;确保数据在客户端和服务器之间的传输过程中不会被窃取或篡改。 HTTPS 的工作原理 客户端发起HTTPS请求&…...

系统中非功能性需求的思考

概要 设计系统时不仅要考虑功能性需求&#xff0c;还要考虑一些非功能性需求&#xff0c;比如&#xff1a; 扩展性可靠性和冗余安全和隐私服务依赖SLA要求 下面对这5项需要考虑的事项做个简单的说明 1. 可扩展性 数据量增长如何扩展&#xff1f; 流量增长如何扩展&#xf…...

力扣第215题“数组中的第K个最大元素”

在本篇文章中&#xff0c;我们将详细解读力扣第215题“数组中的第K个最大元素”。通过学习本篇文章&#xff0c;读者将掌握如何使用快速选择算法和堆排序来解决这一问题&#xff0c;并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释&#xff0c;以便于理解。…...

java.util.function实现原理和Java使用场景【Function、Predicate集合转换过滤,BiConsumer事件处理】

简介 java.util.function 是 Java 8 引入的一个功能包,它包含了多种函数式接口的定义,使得在 Java 中进行函数式编程变得更为方便。下面我将分别介绍 java.util.function 的作用、实现原理、常用 Java 使用场景以及代码示例。 作用 java.util.function 的主要作用是为 Jav…...

《每天5分钟用Flask搭建一个管理系统》 第6章:数据库集成

第6章&#xff1a;数据库集成 6.1 数据库的选择和配置 在Flask中集成数据库&#xff0c;首先需要选择一个数据库系统。常见的选择包括SQLite、MySQL、PostgreSQL等。选择后&#xff0c;需要配置数据库连接字符串。 示例代码&#xff1a;配置数据库 from flask import Flask…...

pandas读取和处理Excel文件的基础应用1

Pandas如何读取Excel文件并处理数据 引言&#xff1a; Pandas是一种常用的数据处理和分析工具&#xff0c;它提供了丰富的函数和方法&#xff0c;方便用户对数据进行清洗、转换和分析。在实际工作中&#xff0c;我们经常需要处理Excel格式的数据文件&#xff0c;本文将介绍如何…...

electron vite react 创建一个项目

要使用 Electron、Vite 和 React 创建一个项目,你可以按照以下步骤操作: 1. 安装 Node.js 和 npm 首先,确保你的计算机上安装了 Node.js 和 npm(Node Package Manager)。你可以从 Node.js 官网 下载并安装。 2. 初始化一个新的项目 在你的工作目录下,创建一个新的文件…...

鸿蒙使用 @Builder扩展出来的布局数据更新没法更新UI

由于业务的复杂&#xff0c;所以我们把相关UI抽离出来。但是数据变化了&#xff0c;没法更新UI Builder MyGridLayout() { } 通过日志打印发现数据的确是更新了&#xff0c;但是UI就没没办法&#xff0c;如何解决呢 Entry Component struct Page35 {// State sArray: bool…...

湖南省教育网络协会莅临麒麟信安调研教育网络数字化建设及教育信创发展情况

6月28日下午&#xff0c;湖南省教育网络协会理事长张智勇、秘书长刘志勇、副理事长黄旭、胡洪波、周中伟等协会相关负责人一行莅临麒麟信安&#xff0c;就湖南省教育网络数字化建设、教育信创工作等主题进行深入调研。麒麟信安副总裁王攀热情接待。 协会成员一行来到麒麟信安展…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

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

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

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...