当前位置: 首页 > 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;就湖南省教育网络数字化建设、教育信创工作等主题进行深入调研。麒麟信安副总裁王攀热情接待。 协会成员一行来到麒麟信安展…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#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;供调用如何按…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

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

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

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...