【dfs序+线段树】P3178 [HAOI2015]树上操作

谁践踏了优雅 2024-03-17 10:06 21阅读 0赞

**这道题，昨天调到一点多都没调出来，眼睛都要瞎了**

**今天看着题解边看边调出来了，但是还是感觉不是很会**

**m d，学的第一道关于树的DS就搞成这样**

**感觉很寄啊**

[P3178 \[HAOI2015\]树上操作 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P3178 _HAOI2015_ - _ _ _ _luogu.com.cn]

题意：

![1a738d9c8af34fd581c7118108232774.png][]

![9eaa0ecdaade4a7981525c67ae084856.png][]

思路：

对于树上的修改操作，我们可以把树的dfs序搞出来，然后在dfs序上修改，这样就把维护树上信息变成维护序列信息了，维护序列的信息用线段树即可

注意，这里的dfs序是每个数仅出现2次，即进栈时记录一次，出栈时记录一次

进栈时记为1，出栈时记为-1

首先维护这么一个序列：

1 1 -1 1 1 -1 1 -1 -1 -1

还有维护dfs序：

1 4 4 2 3 3 5 5 2 1

我们线段树维护的就是这两个序列相乘：

1 4 -4 2 3 -3 5 -5 -2 -1

对于一棵子树，子树就相当于这个序列上的一段区间

操作1是对一个结点u +val，那就是对这个u的进栈的时间戳，即in\[u\]位置+val，对out\[u\]位置-val

操作2是对子树整体+val，那么就相当于对区间整体修改，区间中的数，如果是正的就+val，否则就是-val

即区间加：(区间中的所有1+区间中的所有-1）\*val

操作3就是输出区间和即可

这些用线段树都非常好维护

![3f724d4237a44d18858bafafec83eb82.png][]

![320dc6c5e426487da59967c53466e949.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    struct ty2{
    	int val,add;
    }tree[mxe<<2];
    
    int N,M,u,v,op,x,k,idx=0,tot=0;
    int a[mxn],b[mxn],num[mxn];
    int in[mxn],out[mxn],mp[mxn],head[mxn];
    
    void dfs(int u,int fa){
    	in[u]=++idx;
    	mp[idx]=u;
    	b[in[u]]=1;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    	}
    	out[u]=++idx;
    	mp[idx]=u;
    	b[out[u]]=-1;
    }
    void pushup(int rt){
    	tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt].val=b[l]*a[mp[l]];
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    void pushdown(int rt,int l,int r){
    	int mid=l+r>>1;
    	tree[rt<<1].val+=tree[rt].add*(num[mid]-num[l-1]);
    	tree[rt<<1|1].val+=tree[rt].add*(num[r]-num[mid]);
    	tree[rt<<1].add+=tree[rt].add;
    	tree[rt<<1|1].add+=tree[rt].add;
    	tree[rt].add=0;
    }
    void change(int rt,int l,int r,int x,int k){
    	tree[rt].val+=k;
    	if(l==r) return;
    	int mid=l+r>>1;
    	if(x<=mid) change(rt<<1,l,mid,x,k);
    	else change(rt<<1|1,mid+1,r,x,k);
    }
    void modify(int rt,int l,int r,int x,int y,int k){
    	if(x<=l&&r<=y){
    		tree[rt].add+=k;
    		tree[rt].val+=(num[r]-num[l-1])*k;
    		return;
    	}
    	if(tree[rt].add) pushdown(rt,l,r);
    	int mid=l+r>>1;
    	if(x<=mid) modify(rt<<1,l,mid,x,y,k);
    	if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k);
    	pushup(rt);
    }
    int query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].val;
    	}
    	if(tree[rt].add) pushdown(rt,l,r);
    	int mid=l+r>>1;
    	int res=0;
    	if(x<=mid) res+=query(rt<<1,l,mid,x,y);
    	if(y>mid) res+=query(rt<<1|1,mid+1,r,x,y);
    	return res;
    }
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void solve(){
    	cin>>N>>M;
    	G_init();
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,-1);
    	for(int i=1;i<=idx;i++) num[i]=num[i-1]+b[i];
    	build(1,1,N+N);
    	for(int i=1;i<=M;i++){
    		cin>>op;
    		if(op==1){
    			cin>>x>>k;
    			change(1,1,N+N,in[x],k);
    			change(1,1,N+N,out[x],-k);
    		}else if(op==2){
    			cin>>x>>k;
    			modify(1,1,N+N,in[x],out[x],k);
    		}else{
    			cin>>x;
    			cout<<query(1,1,N+N,1,in[x])<<'\n';
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[P3178 _HAOI2015_ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P3178
[1a738d9c8af34fd581c7118108232774.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/6e67b6cd5e72455c86355a77d001fa09.png
[9eaa0ecdaade4a7981525c67ae084856.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/ba841e053c83467382c48663b86c6ec5.png
[3f724d4237a44d18858bafafec83eb82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/8471849bb9ab4b25b6e57536f3f433e0.png
[320dc6c5e426487da59967c53466e949.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/2dd30535dd5e46f3aa5faac73195bc23.png