bzoj4034&luogu3178 [HAOI2015]树上操作

bzoj4034&luogu3178 [HAOI2015]树上操作

​​ 题目描述

有一棵点数为 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 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 。

模板题：同zjoi2008树的统计

子树修改那个可以id[x]+size[x]-1;因为这肯定是连续区间

#include#define N 110000#define LL long longinline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int y,next;}data[N<<1];struct node1{ int l,r,left,right;LL sum,lazy;}tree[N<<2];int num,size[N],dep[N],fa[N],w[N],id[N],a[N],son[N],h[N],tp[N],n,m,root;void dfs1(int x){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x]==y) continue; fa[y]=x;dep[y]=dep[x]+1;dfs1(y);size[x]+=size[y]; if (size[y]>size[son[x]]) son[x]=y; }}void dfs2(int x,int top){ id[x]=++num;tp[x]=top;w[num]=a[x]; if (son[x]) dfs2(son[x],top); for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (y==fa[x]||y==son[x]) continue; dfs2(y,y); }}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].sum=tree[l].sum+tree[r].sum;}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r; if (l==r) {tree[x].sum=w[l];return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}inline void pushdown(int x){ if (!tree[x].lazy) return; int l=tree[x].left,r=tree[x].right; LL lazy=tree[x].lazy; tree[l].lazy+=lazy;tree[r].lazy+=lazy; tree[l].sum+=(LL)(tree[l].r-tree[l].l+1)*lazy; tree[r].sum+=(LL)(tree[r].r-tree[r].l+1)*lazy; tree[x].lazy=0;}void change(int x,int l1,int r1,int v){ if (l1<=tree[x].l&&r1>=tree[x].r){ tree[x].sum+=(LL)(tree[x].r-tree[x].l+1)*v;tree[x].lazy+=v; return; } int mid=(tree[x].l+tree[x].r)>>1;pushdown(x); if (l1<=mid) change(tree[x].left,l1,r1,v); if (r1>mid) change(tree[x].right,l1,r1,v); update(x);}LL query(int x,int l1,int r1){ if (l1<=tree[x].l&&r1>=tree[x].r) return tree[x].sum; int mid=(tree[x].l+tree[x].r)>>1;pushdown(x);LL tmp1=0,tmp2=0; if (l1<=mid) tmp1=query(tree[x].left,l1,r1); if (r1>mid) tmp2=query(tree[x].right,l1,r1); return tmp1+tmp2;}int main(){ freopen("3178.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。