首页 > 代码库 > 洛谷——P3178 [HAOI2015]树上操作
洛谷——P3178 [HAOI2015]树上操作
https://www.luogu.org/problem/show?pid=3178#sub
题目描述
有一棵点数为 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 <algorithm> 2 #include <cstdio> 3 4 #define LL long long 5 6 using namespace std; 7 8 const LL N(100000+15); 9 const LL M(100000+15); 10 LL n,m,u,v,w,op,val[N]; 11 12 LL head[N],sumedge; 13 struct Edge 14 { 15 LL u,v,next; 16 Edge(LL u=0,LL v=0,LL next=0): 17 u(u),v(v),next(next){} 18 }edge[M<<1]; 19 inline void ins(LL u,LL v) 20 { 21 edge[++sumedge]=Edge(u,v,head[u]); 22 head[u]=sumedge; 23 } 24 25 LL size[N],deep[N],dad[N],son[N],top[N],dfn[N],id[N],cnt; 26 void DFS(LL x,LL father,LL deepth) 27 { 28 deep[x]=deepth; 29 dad[x]=father; 30 size[x]=1; 31 for(LL i=head[x];i;i=edge[i].next) 32 { 33 LL v=edge[i].v; 34 if(dad[x]==v) continue; 35 DFS(v,x,deepth+1); 36 size[x]+=size[v]; 37 if(size[son[x]]<size[v]) son[x]=v; 38 } 39 } 40 void DFS_(LL x,LL Top) 41 { 42 top[x]=Top; 43 id[x]=++cnt,dfn[cnt]=x; 44 if(son[x]) DFS_(son[x],Top); 45 for(LL i=head[x];i;i=edge[i].next) 46 { 47 LL v=edge[i].v; 48 if(dad[x]!=v&&son[x]!=v) DFS_(v,v); 49 } 50 } 51 52 struct Tree 53 { 54 LL l,r,mid,flag,val; 55 }tree[N<<2]; 56 inline void Tree_up(LL now) 57 { 58 tree[now].val=tree[now<<1].val+tree[now<<1|1].val; 59 } 60 void Tree_down(LL now) 61 { 62 tree[now<<1].flag+=tree[now].flag; 63 tree[now<<1].val+=(tree[now].mid-tree[now].l+1)*tree[now].flag; 64 tree[now<<1|1].flag+=tree[now].flag; 65 tree[now<<1|1].val+=(tree[now].r-tree[now].mid)*tree[now].flag; 66 tree[now].flag=0; 67 } 68 void Tree_build(LL now,LL l,LL r) 69 { 70 tree[now].l=l;tree[now].r=r; 71 if(l==r) 72 { 73 tree[now].val=val[dfn[l]]; 74 return ; 75 } 76 tree[now].mid=l+r>>1; 77 Tree_build(now<<1,l,tree[now].mid); 78 Tree_build(now<<1|1,tree[now].mid+1,r); 79 Tree_up(now); 80 } 81 void Tree_change(LL now,LL l,LL r,LL x) 82 { 83 84 if(tree[now].l==l&&tree[now].r==r) 85 { 86 tree[now].flag+=x; 87 tree[now].val+=(r-l+1)*x; 88 return ; 89 } 90 if(tree[now].flag) Tree_down(now); 91 if(tree[now].mid>=r) Tree_change(now<<1,l,r,x); 92 else if(tree[now].mid<l) Tree_change(now<<1|1,l,r,x); 93 else 94 { 95 Tree_change(now<<1,l,tree[now].mid,x); 96 Tree_change(now<<1|1,tree[now].mid+1,r,x); 97 } 98 Tree_up(now); 99 }100 LL Tree_query(LL now,int l,int r)101 {102 if(tree[now].l==l&&tree[now].r==r)103 return tree[now].val;104 if(tree[now].flag) Tree_down(now);105 if(tree[now].mid>=r) return Tree_query(now<<1,l,r);106 else if(tree[now].mid<l) return Tree_query(now<<1|1,l,r);107 else return Tree_query(now<<1,l,tree[now].mid)+Tree_query(now<<1|1,tree[now].mid+1,r);108 }109 110 LL List_query(LL x,LL y)111 {112 LL ret=0;113 for(;top[x]!=top[y];x=dad[top[x]])114 {115 if(deep[top[x]]<deep[top[y]]) swap(x,y);116 ret+=Tree_query(1,id[top[x]],id[x]);117 }118 if(deep[x]<deep[y]) swap(x,y);119 ret+=Tree_query(1,id[y],id[x]);120 return ret;121 }122 123 int if_,ch;124 inline void read (LL &x)125 {126 if_=x=0;ch=getchar();127 for(;ch<‘0‘||ch>‘9‘;ch=getchar())128 if(ch==‘-‘) if_=1;129 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())130 x=x*10+ch-‘0‘;131 if(if_) x=(~x)+1;132 }133 134 int main()135 {136 read(n); read(m);137 for(LL i=1;i<=n;i++)138 read(val[i]);139 for(LL i=1;i<n;i++)140 {141 read(u); read(v);142 ins(u,v),ins(v,u);143 }144 DFS(1,0,1);DFS_(1,1);145 Tree_build(1,1,n);146 for(;m--;)147 {148 read(op);149 if(op==1)150 {151 read(u); read(w);152 Tree_change(1,id[u],id[u],w);153 }154 else if(op==2)155 {156 read(u); read(w);157 Tree_change(1,id[u],id[u]+size[u]-1,w);158 }159 else160 {161 read(u);162 printf("%lld\n",List_query(u,1));163 }164 }165 return 0;166 }
洛谷——P3178 [HAOI2015]树上操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。