[HAOI2015]树上操作 题解
2024-10-21 14:24:35
题目描述
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:
- 操作 1 :把某个节点 x 的点权增加 a 。
- 操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
- 操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
输入格式
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数,表示树中节点的初始权值。
接下来 N-1 行每行两个正整数 from, to , 表示该树中存在一条边 (from, to) 。
再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
输出格式
对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
输入输出样例
输入 #1
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
输出 #1
6
9
13
说明/提示
对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不会超过 10^6 。
一道树链剖分模板题。。。,比洛谷树链剖分模板题还简单
【模板】树链剖分需要支持路径修改,子树修改,子树查询和路径查询
这道题只需要支持单点修改,子树修改和路径查询,而且路径的左端点还固定为1,其实这道题应该是蓝题的。。。
哦对了,重要的事情说三遍:
开long long,开long long,开long long
不会树链剖分的小伙伴可以参考以下博客
想联系树链剖分的同学们也可以参考以下题目
好了废话不多数,放代码吧
代码如下:
#include<bits/stdc++.h>
using namespace std;
struct SYM{
int to,next;
}edge[];
struct ASJ{
long long sum;
long long lz;
}tree[];
int head[],tot;
int n,m;
int w[],dep[],fa[],son[],siz[],top[],wet[],id[];
void addedge(int x,int y){
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
void build(int i,int l,int r){ //建树
if(l==r){
tree[i].sum=wet[l];
return ;
}
int mid=(l+r)/;
build(*i,l,mid); //左儿子
build(*i+,mid+,r); //右儿子
tree[i].sum=(tree[*i].sum+tree[*i+].sum);
}
void pushdown(int i,long long len){ //LAZY下传
tree[*i].lz+=tree[i].lz;
tree[*i+].lz+=tree[i].lz;
tree[*i].sum+=(tree[i].lz*(len-len/));
tree[*i+].sum+=(tree[i].lz*(len/));
tree[i].lz=; //别忘了清零
}
void update(int i,int l,int r,int L,int R,long long k){//更新操作
if(l>=L&&r<=R){
tree[i].sum+=k*(r-l+);
tree[i].lz+=k;
return ;
}
int mid=(l+r)/;
pushdown(i,(r-l+)); //下传LAZY
if(L<=mid) update(*i,l,mid,L,R,k);
if(R>mid) update(*i+,mid+,r,L,R,k);
tree[i].sum=tree[*i].sum+tree[*i+].sum;
}
long long query(int i,int l,int r,int L,int R){//查询操作
long long ans=;
if(l>=L&&r<=R){
return tree[i].sum;
}
int mid=(l+r)/;
pushdown(i,(r-l+));
if(L<=mid) ans+=query(*i,l,mid,L,R);
if(R>=mid+) ans+=query(*i+,mid+,r,L,R);
return ans;
}
//----------------------------------------------------------------上面是线段树
void dfs1(int now,int from){ //处理dep,fa,siz,以及重儿子son
dep[now]=dep[from]+;
fa[now]=from;
int maxson=-;
siz[now]=;
for(int i=head[now];i;i=edge[i].next){
int v=edge[i].to;
if(v==from) continue;
dfs1(v,now);
siz[now]+=siz[v];
if(siz[v]>maxson){
son[now]=v;
maxson=siz[v];
}
}
}
int cnt;
void dfs2(int now,int topr){ //处理重链链顶top,新点id,新点权值wet
id[now]=++cnt;
top[now]=topr;
wet[cnt]=w[now];
if(!son[now]) return;
dfs2(son[now],topr); //先处理重儿子,再处理轻儿子
for(int i=head[now];i;i=edge[i].next){
int v=edge[i].to;
if(v==fa[now]||v==son[now]) continue;
dfs2(v,v); //每个轻儿子都是一个新的链顶,别忘了换链顶!!!
}
}
void update1(int x,int k){
update(,,n,id[x],id[x]+siz[x]-,k); //子树是连续的所以左节点id[x],右节点id[x]+siz[x]-1
}
long long q1(int x,int y){ //这里我写的有点麻烦,因为一个点固定为根1,所以其实可以省略一些,不过这里的代码是可以应用于每一个树链剖分路经查询的
long long ans=;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(,,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(,,n,id[x],id[y]);
return ans;
}
int main(){
freopen("sscz.in","r",stdin);
freopen("sscz.out","w",stdout);
int no,x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&w[i]);
for(int i=;i<n;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs1(,);
dfs2(,);
build(,,n);
while(m--){
scanf("%d",&no);
if(no==){
scanf("%d%d",&x,&y);
update(,,n,id[x],id[x],y); //单点修改
}
if(no==){
scanf("%d%d",&x,&y); //子树修改
update1(x,y);
}
if(no==){ //路径查询
scanf("%d",&x);
printf("%lld\n",q1(x,));
}
}
}
最新文章
- awk命令和grep命令的使用
- python pip方式安装selenium
- java时间计算,获取某月第一天和最后一天
- wamp2.5 局域网无法访问问题
- 多个Excel文件快速导入到DB里面
- 在Unity中如何取得一个Box的Bounds
- Android服务之Service(其一)
- 字符串,int,十六进制间转换
- scau 8633 回文划分
- VMWare Workstation的命令
- hdu 3282 Running Median
- NTP服务及时间同步(CentOS6.x)
- JavaEE(7) - JMS消息事务和异常
- Python爬取百度贴吧数据
- 201521123017 《Java程序设计》第9周学习总结
- (MariaDB)MySQL数据类型详解和存储机制
- 20175333曹雅坤 实验二 Java面向对象程序设计
- poj 3126 Prime Path bfs
- 使用 IIS 在 Windows 上托管 ASP.NET Core2.0
- luogu5021 [NOIp2018]赛道修建 (二分答案+dp(贪心?))
热门文章
- Tips on Java
- vigil deb 包制作
- 洛谷 P2897 【蚯蚓】 题解
- 解决IE报错:Locale &#39;chinese&#39; is not well-formed,或RangeError: 区域设置“chinese”的格式不正确的问题
- SP19997 MOON2 - Moon Safari (Hard) 【数论,多项式】
- 如果判断条件过多,可以直接在computed里面去返回需要判断的数据
- Linux系统学习(二)一Linux基本操作
- 移动端 - adb shell常用命令
- maven依赖 dependency中scope=compile 和 provided区别
- css3实现左侧固宽,右侧随着屏幕,右侧随着屏幕变化而变化