博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[HAOI2015]树上操作
阅读量:6496 次
发布时间:2019-06-24

本文共 2540 字,大约阅读时间需要 8 分钟。

题目描述

有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式:

 

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。

 

输出格式:

 

对于每个询问操作,输出该询问的答案。答案之间用换行隔开。

 

输入输出样例

输入样例#1:
5 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3
输出样例#1:
6913

说明

对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不

会超过 10^6 。

树链剖分。

代码实现:

1 #include
2 #include
3 #define ls k*2 4 #define rs k*2+1 5 #define LL long long 6 #define maxn 100010 7 using namespace std; 8 LL a,b,c,ans; 9 LL n,m,l,hs,nl;10 LL s[maxn],h[maxn];11 LL k[maxn],f[maxn],d[maxn],p[maxn],sz[maxn],is[maxn],ct[maxn];12 struct node{LL s,n;}e[maxn<<1];13 struct tree{LL l,r,s,f;}t[maxn<<2];14 inline void add(LL x,LL y){e[++hs]=(node){y,h[x]};h[x]=hs;}15 void dfs1(LL x,LL y,LL st){16 f[x]=y;d[x]=st;sz[x]=1;17 for(LL i=h[x];i;i=e[i].n)18 if(e[i].s!=y){19 dfs1(e[i].s,x,st+1);20 sz[x]+=sz[e[i].s];21 if(sz[e[i].s]>sz[is[x]]) is[x]=e[i].s;22 }23 }24 void dfs2(LL x){25 s[++l]=k[x];p[x]=l;26 if(is[x]){27 ct[is[x]]=ct[x];28 dfs2(is[x]);29 }30 for(LL i=h[x];i;i=e[i].n)31 if(e[i].s!=f[x]&&e[i].s!=is[x]){32 ct[e[i].s]=e[i].s;33 dfs2(e[i].s);34 }35 }36 void build(LL k,LL l,LL r){37 t[k].l=l;t[k].r=r;38 if(l==r){t[k].s=s[++nl];return;}39 LL mid=(l+r)>>1;40 build(ls,l,mid);41 build(rs,mid+1,r);42 t[k].s=t[ls].s+t[rs].s;43 }44 void heritage(LL k){45 t[ls].s+=(t[ls].r-t[ls].l+1)*t[k].f,t[ls].f+=t[k].f;46 t[rs].s+=(t[rs].r-t[rs].l+1)*t[k].f,t[rs].f+=t[k].f;47 t[k].f=0;48 }49 void change(LL k,LL l,LL r,LL al,LL ar,LL am){50 if(l==al&&r==ar){t[k].f+=am,t[k].s+=(r-l+1)*am;return;}51 if(t[k].f) heritage(k);52 LL mid=(l+r)>>1;53 if(al<=mid) change(ls,t[ls].l,t[ls].r,al,min(ar,mid),am);54 if(ar>mid) change(rs,t[rs].l,t[rs].r,max(al,mid+1),ar,am);55 t[k].s=t[ls].s+t[rs].s;56 }57 LL query(LL k,LL l,LL r,LL al,LL ar){58 if(l==al&&r==ar) return t[k].s;59 if(t[k].f) heritage(k);60 LL mid=(l+r)>>1,ans=0;61 if(al<=mid) ans+=query(ls,t[ls].l,t[ls].r,al,min(ar,mid));62 if(ar>mid) ans+=query(rs,t[rs].l,t[rs].r,max(al,mid+1),ar);63 return ans;64 }65 int main(){66 scanf("%lld%lld",&n,&m);67 for(LL i=1;i<=n;i++) scanf("%lld",&k[i]);68 for(LL i=1;i

题目来源:洛谷

转载于:https://www.cnblogs.com/J-william/p/6381929.html

你可能感兴趣的文章
25 个 Linux 性能监控工具
查看>>
C#程序员整理的Unity 3D笔记(十三):Unity 3D基于组件的思想
查看>>
Tengine-2.1.1 ngx_http_concat_module 400问题
查看>>
Windows中挂载安装ISO文件
查看>>
Wayland 1.0发布
查看>>
golang的goroutine是如何实现的?
查看>>
乐视云基于Kubernetes的PaaS平台建设
查看>>
R 学习笔记《十》 R语言初学者指南--图形工具
查看>>
PHP通过读取DOM抓取信息
查看>>
DICOM医学图像处理:DICOM网络传输
查看>>
nio和传统Io的区别
查看>>
移动端网页布局中需要注意事项以及解决方法总结
查看>>
(原创)Linux下查看系统版本号信息的方法
查看>>
oracle
查看>>
redis使用过程中主机内核层面的一些优化
查看>>
我也要谈谈大型网站架构之系列(2)——纵观历史演变(下)
查看>>
OctoberCMS目录结构-基于Laravel
查看>>
大话设计模式(Golang) 二、策略模式
查看>>
JQuery页面随滚动条动态加载效果实现
查看>>
Jackson 处理is开头的字段
查看>>