P3178 [HAOI2015]樹上操作

題意：

題解：

這已經是很裸的樹鏈剖分了。。。
直接套模板

代碼：

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define int long long const int maxn=2e5+10; inline int read() {int s=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')w=-w;c=getchar();}while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}return s*w; } int n,m; int e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn]; int a[maxn<<2],laz[maxn<<2]; int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn]; int res=0; //id[]表示時間戳（即在鏈當中的編號） //dep[]表示該節點的深度 //siz[]表示該節點子樹的大小【方便修改子樹數值時調用線段樹】 //top[]表示重量開端 #define mid ((l+r)>>1) #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define len (r-l+1) inline void add(int x,int y)//鏈式前向星 {to[++e]=y;nex[e]=beg[x];beg[x]=e; } //-----------------------以下為線段樹----------------------------------- inline void build(int rt,int l,int r) {if(l==r){a[rt]=wt[l];return;}build(lson);build(rson);a[rt]=(a[rt<<1]+a[rt<<1|1]); } inline void pushdown(int rt,int lenn) {laz[rt<<1]+=laz[rt];laz[rt<<1|1]+=laz[rt];a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));a[rt<<1|1]+=laz[rt]*(lenn>>1);laz[rt]=0; } inline void query(int rt,int l,int r,int L,int R) {if(L<=l&&r<=R){res+=a[rt];return;}else{if(laz[rt])pushdown(rt,len);if(L<=mid)query(lson,L,R);if(R>mid)query(rson,L,R);} } void update(int node,int left,int right,int pos,int v) {if(left==right){a[node]+=v;return ;}int midn=(left+right)/2;if(laz[node])//注意：單點修改可能會影響lazy標記，需要處理一下 pushdown(node,right-left+1);if(pos<=midn){update(2*node,left,midn,pos,v);}else{update(2*node+1,midn+1,right,pos,v);}a[node]=a[2*node]+a[2*node+1]; } inline void updata(int rt,int l,int r,int L,int R,int k) {if(L<=l&&r<=R){laz[rt]+=k;a[rt]+=k*len;}else{if(laz[rt])pushdown(rt,len);if(L<=mid)updata(lson,L,R,k);if(R>mid)updata(rson,L,R,k);a[rt]=(a[rt<<1]+a[rt<<1|1]);} } //-----------------------以上為線段樹----------------------------------- inline void dfs1(int x,int f,int deep) {dep[x]=deep;fa[x]=f;siz[x]=1;int maxson=-1;for(register int i=beg[x];i;i=nex[i]){int y=to[i];if(y==f)continue;dfs1(y,x,deep+1);siz[x]+=siz[y];if(siz[y]>maxson)son[x]=y,maxson=siz[y];} } inline void dfs2(int x,int topf) {id[x]=++cnt;wt[cnt]=w[x];top[x]=topf;if(!son[x])return;dfs2(son[x],topf);for(register int i=beg[x];i;i=nex[i]){int y=to[i];if(y==fa[x]||y==son[x])continue;dfs2(y,y);} } inline int qRange(int x,int y) {int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);res=0;query(1,1,n,id[top[x]],id[x]);ans+=res;x=fa[top[x]];}if(dep[x]>dep[y])swap(x,y);res=0;query(1,1,n,id[x],id[y]);ans+=res;return ans; } signed main() {n=read();m=read();for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<n;i++){int a,b;a=read();b=read();add(a,b);add(b,a);}dfs1(1,0,1);dfs2(1,1);build(1,1,n);while(m--){int k,x,y;k=read();if(k==1){x=read();y=read();update(1,1,n,id[x],y);}if(k==2){x=read();y=read();updata(1,1,n,id[x],id[x]+siz[x]-1,y);}if(k==3){x=read();printf("%lld\n",qRange(1,x));}}return 0; }

總結

以上是生活随笔為你收集整理的P3178 [HAOI2015]树上操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。