Description

有一棵點(diǎn)數(shù)為 N 的樹(shù)，以點(diǎn) 1 為根，且樹(shù)點(diǎn)有邊權(quán)。然后有 M 個(gè) 操作，分為三種： 操作 1 ：把某個(gè)節(jié)點(diǎn) x 的點(diǎn)權(quán)增加 a 。 操作 2 ：把某個(gè)節(jié)點(diǎn) x 為根的子樹(shù)中所有點(diǎn)的點(diǎn)權(quán)都增加 a 。 操作 3 ：詢問(wèn)某個(gè)節(jié)點(diǎn) x 到根的路徑中所有點(diǎn)的點(diǎn)權(quán)和。

Solution

本來(lái)是一道裸的樹(shù)剖，不過(guò)其實(shí)是可以歐拉序列搞一搞的

對(duì)于每個(gè)節(jié)點(diǎn)在dfs序中記錄2次，入棧的時(shí)候加上，出棧的時(shí)候減去

那么一個(gè)點(diǎn)到根的路徑上的信息就是dfs序里它第一次出現(xiàn)的位置的前綴和

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define MAXN 100005 using namespace std; typedef long long LL; int n,m,w[MAXN],head[MAXN],cnt=0,q[MAXN*2],in[MAXN],out[MAXN],dfn_clock=0; struct Node1 {int next,to; }Edges[MAXN*2]; struct Node2 {int l,r,num;LL sum,lazy; }t[MAXN*8]; int read() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } void addedge(int u,int v) {Edges[++cnt].next=head[u];head[u]=cnt;Edges[cnt].to=v; } void dfs(int u,int f) {q[++dfn_clock]=u;in[u]=dfn_clock;for(int i=head[u];~i;i=Edges[i].next){int v=Edges[i].to;if(v==f)continue;dfs(v,u);}q[++dfn_clock]=-u;out[u]=dfn_clock; } void update(int idx) {t[idx].sum=t[idx<<1].sum+t[idx<<1|1].sum; } void pushdown(int idx) {if(t[idx].lazy&&t[idx].l!=t[idx].r){t[idx<<1].lazy+=t[idx].lazy;t[idx<<1|1].lazy+=t[idx].lazy;t[idx<<1].sum+=1LL*t[idx].lazy*t[idx<<1].num;t[idx<<1|1].sum+=1LL*t[idx].lazy*t[idx<<1|1].num;t[idx].lazy=0;} } void build(int idx,int l,int r) {t[idx].l=l,t[idx].r=r;if(l==r){t[idx].lazy=0;if(q[l]>0){t[idx].sum=w[q[l]],t[idx].num=1;return;}else{t[idx].sum=-w[-q[l]],t[idx].num=-1;return;}}int mid=(l+r)>>1;build(idx<<1,l,mid),build(idx<<1|1,mid+1,r);t[idx].num=t[idx<<1].num+t[idx<<1|1].num;update(idx); } void add(int idx,int l,int r,int v) {if(l<=t[idx].l&&r>=t[idx].r){t[idx].lazy+=v;t[idx].sum+=1LL*t[idx].num*v;return;}pushdown(idx);int mid=(t[idx].l+t[idx].r)>>1;if(r<=mid)add(idx<<1,l,r,v);else if(l>mid)add(idx<<1|1,l,r,v);else add(idx<<1,l,r,v),add(idx<<1|1,l,r,v);update(idx); } LL query(int idx,int l,int r) {if(l<=t[idx].l&&r>=t[idx].r)return t[idx].sum;pushdown(idx);int mid=(t[idx].l+t[idx].r)>>1;if(r<=mid)return query(idx<<1,l,r);else if(l>mid)return query(idx<<1|1,l,r);else return query(idx<<1,l,r)+query(idx<<1|1,l,r); } int main() {n=read(),m=read();memset(head,-1,sizeof(head));for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<n;i++){int u=read(),v=read();addedge(u,v);addedge(v,u);}dfs(1,0),build(1,1,dfn_clock);for(int i=1;i<=m;i++){int opt=read(),x=read(),a;if(opt==1)a=read(),add(1,in[x],in[x],a),add(1,out[x],out[x],a);else if(opt==2)a=read(),add(1,in[x],out[x],a);else printf("%lld\n",query(1,1,in[x]));}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Zars19/p/6924766.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 4034][HAOI2015]树上操作（欧拉序列+线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。