BZOJ 4034 [HAOI2015]T2 树链剖分+线段树

题意: 一棵以1为根的树，有n个节点，，m个操作。 第一种单点修改。 第二种修改一个点的子树。 第三种询问一个点到根的路径上所有点的权值和。 解析: 看到有人在做我就跑过来看了一下，看完题发现这不SB题么- – 于是就写了下，差点被出题人气死。 TMD 那个 fr , to 难道就是逗我玩的？ 你丫fr,to不代表有向边？ 这么出题不会掉RP？ 改了20分钟就这错了？你逗我？ 第一种操作略 第二种操作修改子树…dfs序。 第三种链剖完之后直接找就行了。 复杂度O(nlog^2n); 代码:

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 100100#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1using namespace std;typedef long long ll;int n,m,cnt,tot;ll a[N],val[N];int head[N];int dep[N],son[N],fa[N],siz[N],tim[N],end[N],top[N];struct node{int from,to;int next;}edge[N<<1];void init(){memset(head,-1,sizeof(head));cnt=1,dep[1]=1;}void edgeadd(int from,int to){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}void dfs1(int now){son[now]=-1,siz[now]=1;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==fa[now])continue;fa[to]=now;dep[to]=dep[now]+1;dfs1(to);siz[now]+=siz[to];if(son[now]==-1||siz[son[now]]<siz[to])son[now]=to;}}void dfs2(int now,int tp){top[now]=tp,tim[now]=++tot;if(son[now]!=-1)dfs2(son[now],tp);for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==son[now]||to==fa[now])continue;dfs2(to,to);}end[now]=tot;}ll sum[N<<2],col[N<<2];void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int rt,int l,int r){if(col[rt]){int mid=(l+r)>>1;sum[rt<<1]+=col[rt]*(ll)(mid-l+1);sum[rt<<1|1]+=col[rt]*(ll)(r-mid);col[rt<<1]+=col[rt];col[rt<<1|1]+=col[rt];col[rt]=0;}}void build(int l,int r,int rt){if(l==r){sum[rt]=val[l];return;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);}void update_pt(int p,ll v,int l,int r,int rt){if(l==r){sum[rt]+=v;return;}int mid=(l+r)>>1;pushdown(rt,l,r);if(p<=mid)update_pt(p,v,lson);else update_pt(p,v,rson);pushup(rt);}void update_seg(ll v,int L,int R,int l,int r,int rt){if(L<=l&&r<=R){col[rt]+=v;sum[rt]+=v*(ll)(r-l+1);return;}int mid=(l+r)>>1;pushdown(rt,l,r);if(L<=mid)update_seg(v,L,R,lson);if(R>mid)update_seg(v,L,R,rson);pushup(rt);}ll query_seg(int L,int R,int l,int r,int rt){ll ret=0;if(L<=l&&r<=R){return sum[rt];}int mid=(l+r)>>1;pushdown(rt,l,r);if(L<=mid)ret+=query_seg(L,R,lson);if(R>mid)ret+=query_seg(L,R,rson);return ret;}ll query(int x){ll ret=0;while(top[x]){int l=tim[top[x]],r=tim[x];ret+=query_seg(l,r,1,n,1);x=fa[top[x]];}return ret;}int main(){init();scanf(“%d%d”,&n,&m);for(int i=1;i<=n;i++)scanf(“%lld”,&a[i]);for(int i=1;i<n;i++){int x,y;scanf(“%d%d”,&x,&y);edgeadd(x,y);edgeadd(y,x);}dfs1(1);dfs2(1,1);for(int i=1;i<=n;i++)val[tim[i]]=a[i];build(1,n,1);for(int i=1;i<=m;i++){int opt,x;ll a;scanf(“%d”,&opt);if(opt==1){scanf(“%d%lld”,&x,&a);update_pt(tim[x],a,1,n,1);}else if(opt==2){scanf(“%d%lld”,&x,&a);update_seg(a,tim[x],end[x],1,n,1);}else{scanf(“%d”,&x);printf(“%lld\n”,query(x));}}}

人，总是很难改正自己的缺点，