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

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

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

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

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...