我说我是不是完蛋了啊... ...昨天考试线段树写错，调了好久才调回来；今天做这道树链剖分辣鸡操作题，TM写错了4个地方！先是建树为了省常数打了一个build结果初值赋错了，然后又是线段树！getmax和getsum错的还不是一个地方！最后我发现update赋的不是dfn[x]而是x！再这样下去我是不是有一天连for循环都不会打了啊！！！

　　　　好吧我是用Windows的Devcpp写的，丑了一点啊。

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #define ls (x<<1) #define rs (x<<1|1) using namespace std; const int N = 30010; struct Node{int to,next;}E[N<<1]; int n,m,fa[N],top[N],val[N],T[N<<4],T2[N<<4],son[N],size[N],rec[N],dfn[N],tot,dep[N],num,head[N]; inline int gi() {int x=0,res=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*res; } inline void link(int u,int v) {E[++tot]=(Node){v,head[u]};head[u]=tot;E[++tot]=(Node){u,head[v]};head[v]=tot; } inline void dfs1(int x,int fat) {dep[x]=dep[fat]+1;fa[x]=fat;size[x]++;for(int e=head[x];e;e=E[e].next){if(E[e].to==fat)continue;dfs1(E[e].to,x);size[x]+=size[E[e].to];if(size[E[e].to]>size[son[x]])son[x]=E[e].to;} } inline void dfs2(int x,int tp) {top[x]=tp;dfn[x]=++num;rec[num]=x;if(!son[x])return;dfs2(son[x],tp);for(int e=head[x];e;e=E[e].next)if(E[e].to!=fa[x]&&E[e].to!=son[x])dfs2(E[e].to,E[e].to); } inline void build(int x,int l,int r) {if(l==r){T2[x]=T[x]=val[rec[l]];return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);T2[x]=T2[ls]+T2[rs];T[x]=max(T[ls],T[rs]); } inline int gc() {char ch=getchar();while(ch<'A'||ch>'Z')ch=getchar();if(ch=='C')return 1;if(ch=='Q')ch=getchar();if(ch=='M')return 2;if(ch=='S')return 3; } inline void update(int x,int l,int r,int xp,int v) {if(l==r){T[x]=T2[x]=v;return;}int mid=(l+r)>>1;if(xp<=mid)update(ls,l,mid,xp,v);else update(rs,mid+1,r,xp,v);T2[x]=T2[ls]+T2[rs];T[x]=max(T[ls],T[rs]); } inline int getmax(int x,int l,int r,int xl,int xr) {if(xl<=l && r<=xr)return T[x];int mid=(l+r)>>1;if(xr<=mid)return getmax(ls,l,mid,xl,xr);else if(xl>mid)return getmax(rs,mid+1,r,xl,xr);return max(getmax(ls,l,mid,xl,mid),getmax(rs,mid+1,r,mid+1,xr)); } inline int gmax(int u,int v) {int Ans=-N*N;while(top[u]^top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);Ans=max(Ans,getmax(1,1,n,dfn[top[u]],dfn[u]));u=fa[top[u]];}if(dep[u]<dep[v])swap(u,v);Ans=max(Ans,getmax(1,1,n,dfn[v],dfn[u]));return Ans; } inline int getsum(int x,int l,int r,int xl,int xr) {if(xl<=l && r<=xr)return T2[x];int mid=(l+r)>>1;if(xr<=mid)return getsum(ls,l,mid,xl,xr);else if(xl>mid)return getsum(rs,mid+1,r,xl,xr);else return getsum(ls,l,mid,xl,mid)+getsum(rs,mid+1,r,mid+1,xr); } inline int gsum(int u,int v) {int Ans=0;while(top[u]^top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);Ans+=getsum(1,1,n,dfn[top[u]],dfn[u]);u=fa[top[u]];}if(dep[u]<dep[v])swap(u,v);Ans+=getsum(1,1,n,dfn[v],dfn[u]);return Ans; } int main() {n=gi();for(int i=1;i<n;++i)link(gi(),gi());for(int i=1;i<=n;++i)val[i]=gi();dfs1(1,1);dfs2(1,1);build(1,1,n);m=gi();while(m--){int type=gc(),x=gi(),y=gi();switch(type){case 1:{update(1,1,n,dfn[x],y);break;}case 2:{printf("%d\n",gmax(x,y));break;}case 3:{printf("%d\n",gsum(x,y));break;}default:{break;}}} }

　　

转载于:https://www.cnblogs.com/fenghaoran/p/6623012.html

总结

以上是生活随笔为你收集整理的BZOJ1036 (其实这只是一份板子)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。