首页 > 代码库 > 洛谷 P3178 BZOJ 4034 [HAOI2015]树上操作
洛谷 P3178 BZOJ 4034 [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 ） 。
输出格式：
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
输入输出样例
5 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3
6913
说明
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不
会超过 10^6 。
吐槽
今晚真是填坑之夜呀！一连填了3个一个月以上的老坑！
这题和我上一篇博文说的悲惨程度差不多——
是的，你没有看错，还有[Next Page]这种东西……5月初我就开始做这题了……
人越急越写不出东西，所以遇到某些题卡住了，可以搁置一下，过段时间再来写，但是如果第二次冷静下来还是写错，那么就是脑子里的东西错了……
我观察洛谷给的错误情况，除了CE之类的，剩下的错误都是在50行以后，这说明我写的程序的持久性出了问题(不是可持久，是持久)，一些维护修改的东西出错了。
树剖方面
两个dfs第一次调用之后就不再用它了，还有询问时opt3轻重链向上跳的过程，前50个询问都能处理的挺好，不太可能出问题。
就剩修改操作了，opt1和opt2两个函数里都只有一句话，反复检查没有问题我为什么一句话都要反复检查……，于是bug被限定到了线段树部分——
线段树方面
首先是建树，按照dfs序获取轻重链相连组成的序列是在树剖的dfs2部分实现的，获取序列a之后maketree只调用了一次，建出来的线段树毕竟也坚持了50个询问，基本排除出bug的可能。
然后是含有修改的一堆函数，极有可能出bug。询问函数query，表面上不修改线段树，但是其中有一个pushdown啊，可能出错；更新函数change，这个就直接是更改线段树啊！高危！最后是前面两者都调用了的pushdown，简简单单6行，好像没毛——不对，前天写维护序列这题的时候，它的双lazy和我预想的不太一样啊，嗯，极危！先从它查起！
大概确定了出bug范围，剩下的就好搞了，直接找原来写的模板对比。
（一段时间后）
”他丫的我半年前学的线段树lazy是假的，更重要的是我还用它A了不知道多少水题，越错越深，查错时完全忽略了这里……“
我就不把错误的pushdown放上来误导大家了。
非常兴奋地改了这里，迫不及待地交了上去，50分。我居然忘了加long long！为了省事。大家在我的代码开头可以看到一个神奇的define……
解题思路
就是裸的树剖，可以看洛谷的题解百科 。
这题的询问比较方便跳链，于是我偷了个小懒，opt3没套模板，做了个小优化，省时省力。
源代码
#include<vector>#include<cstdio>#include<algorithm>#define int long long using namespace std;int n,m;struct Edge{ int next,to;}e[200010];int cnt=1,head[100010]={0};void add(int u,int v){ e[cnt]={head[u],v}; head[u]=cnt++;}struct Tree{ int w; int fa; vector<int> son; int num_to; int wson; int top; int id;}t[100010];long long a[100010]={0};int dfs1(int fa,int u){ t[u].fa=fa; t[u].num_to=1; for(int i=head[u],maxn=-1;i;i=e[i].next) { int v=e[i].to; if(v==fa) continue; t[u].son.push_back(v); int temp=dfs1(u,v); t[u].num_to+=temp; if(temp>maxn) { maxn=temp; t[u].wson=v; } } return t[u].num_to;}int id=1;void dfs2(int top,int u){ t[u].top=top; t[u].id=id; a[id]=t[u].w; int sz=t[u].son.size(); if(!sz) return; id++; dfs2(top,t[u].wson); for(int i=0;i<sz;i++) { int v=t[u].son[i]; if(v==t[u].wson) continue; id++; dfs2(v,v); }}struct SegTree{ int l,r; long long sum;}s[1000010];long long lazy[1000010]={0};void pushdown(int node)//这个pushdown是真的了{ if(!lazy[node])return; int lson=node<<1,rson=node<<1|1; s[lson].sum+=lazy[node]*(s[lson].r-s[lson].l+1); s[rson].sum+=lazy[node]*(s[rson].r-s[rson].l+1); lazy[lson]+=lazy[node]; lazy[rson]+=lazy[node]; lazy[node]=0;}void maketree(int node,int l,int r){ if(l==r) { s[node]={l,r,a[l]}; return; } int mid=l+r>>1; maketree(node<<1,l,mid); maketree(node<<1|1,mid+1,r); s[node]={l,r,s[node<<1].sum+s[node<<1|1].sum};}void change(int x,int l,int r,int k){ if(r<s[x].l||s[x].r<l)return; if(l<=s[x].l&&s[x].r<=r) { s[x].sum+=k*(s[x].r-s[x].l+1); lazy[x]+=k; return; } pushdown(x); int lson=x<<1,rson=x<<1|1; change(lson,l,r,k); change(rson,l,r,k); s[x].sum=s[lson].sum+s[rson].sum;}long long query(int x,int l,int r){ if(r<s[x].l||s[x].r<l)return 0; if(l<=s[x].l&&s[x].r<=r) { return s[x].sum; } pushdown(x); int lson=x<<1,rson=x<<1|1; return query(lson,l,r)+query(rson,l,r);}inline void opt1(int x,int k){ change(1,t[x].id,t[x].id,k);}inline void opt2(int x,int k){ change(1,t[x].id,t[x].id+t[x].num_to-1,k);}inline void opt3(int x){ long long ans=0; while(x) { ans+=query(1,t[t[x].top].id,t[x].id); x=t[t[x].top].fa; } printf("%lld\n",ans);}main(){ //freopen("test.in","r",stdin); //freopen("haoi2015_t21.out","w",stdout);//在cogs提交的标记历历在目…… scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&t[i].w); for(int i=1,u,v;i<n;i++) { scanf("%lld%lld",&u,&v); add(u,v); add(v,u); } dfs1(0,1); dfs2(1,1); maketree(1,1,n); for(int i=1,mode,x,y;i<=m;i++) { scanf("%lld",&mode); if(mode==1) { scanf("%lld%lld",&x,&y); opt1(x,y); } else if(mode==2) { scanf("%lld%lld",&x,&y); opt2(x,y); } else { scanf("%lld",&x); opt3(x); } } return 0;}
洛谷 P3178 BZOJ 4034 [HAOI2015]树上操作