【dfs序+线段树】求和

「爱情、让人受尽委屈。」 2024-03-17 10:23 84阅读 0赞

**今天终于把昨天的任务给写了**

**呃呃**

[C-求和\_2021秋季算法入门班第十三章习题：LCA (nowcoder.com)][C-_2021_LCA _nowcoder.com]

题意：

![2e5ca05969114bfbbcfdaa5dd357a21a.png][]

思路：

树上操作，考虑把树转化为序列，在序列上用DS维护

对这颗树做一遍dfs，得到dfn序（只记录进栈的顺序，每个结点只出现一次），然后对于操作：

操作1：就是对序列进行单点修改，对u的位置进行修改

操作2：因为一棵子树对应序列中的一个区间，因此就是用线段树进行区间修改，区间的长度就是子树大小，因此也可以把子树的大小预处理出来

Code：

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

[C-_2021_LCA _nowcoder.com]: https://ac.nowcoder.com/acm/contest/27836/C
[2e5ca05969114bfbbcfdaa5dd357a21a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/39711213a88842428bad1b5a8dba65ac.png