LibreOJ-dfs序2 (dfs序，线段树）

题目描述

给一棵有根树，这棵树由编号为1~N 的 N个结点组成。根结点的编号为R。每个结点都有一个权值，结点 的权值为 。 接下来有 M组操作，操作分为两类：

1 a x，表示将结点 的子树上所有结点的权值增加 ；
2 a，表示求结点 的子树上所有结点的权值之和。

输入格式

第一行有三个整数 N,M和R。
第二行有 N个整数，第 i个整数表示 vi。
在接下来的 N-1行中，每行两个整数，表示一条边。
在接下来的 M行中，每行一组操作。

输出格式

对于每组 2 a操作，输出一个整数，表示「以结点 a为根的子树」上所有结点的权值之和。

用到了dfs序，两个数组 st[ ] ，en[ ] 储存每个点遍历的出入时间，通过时间可算出子树节点。
通过 mp[ ] 数组，找到结点与树的对应（映射）
用线段树的区间修改和区间查询，并结合 st[ ] , en[ ] 数组，找到所用的区间。

• 区间修改时标记 lazy[ ] 数组，查询时再向下传递。

代码↓

#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 5; vector<int> q[N]; int st[N],en[N],tmp=0; int n,m,r,b[N]; long long sum[N<<2],lazy[N<<2]; int mp[N]; void dfs(int u, int fa) {  st[u]=++tmp;  mp[tmp] = u; for(auto v:q[u]) { if(v==fa) continue; dfs(v,u); }  en[u]=tmp; } int a[1005],c[1005]; void pushup(int i) {  sum[i]=sum[i<<1]+sum[i<<1|1]; } void up(int i,long long len,long long v) {  sum[i]+=len * v;  lazy[i]+=v; } void pushdown(int i,int l,int r) { int mid=(l+r)/2; if(lazy[i]) { up(i<<1,mid-l+1,lazy[i]); up(i<<1|1,r-mid,lazy[i]);   lazy[i] = 0; } } void build(int i,int l,int r) { if(l==r) {   sum[i] = b[mp[l]]; return ; } int mid=(l+r)/2; build(i<<1,l,mid); build(i<<1|1,mid+1,r); pushup(i); } //区间修改 void zeng(int i,int ql,int qr,int l,int r,int v) { if(ql<=l && qr >=r) { up(i,r-l+1,v); return ; } int mid=(l+r)/2; pushdown(i,l,r); if(ql<=mid) zeng(i<<1,ql,qr,l,mid,v); if(qr>mid) zeng(i<<1|1,ql,qr,mid+1,r,v); pushup(i); } //区间查询 long long he(int i,int ql,int qr,int l,int r) { if(ql<=l && qr >=r) { return sum[i]; } int mid=(l+r)/2; pushdown(i,l,r); long long ans = 0; if(ql<=mid)   ans+=he(i<<1,ql,qr,l,mid); if(qr>mid)   ans+=he(i<<1|1,ql,qr,mid+1,r); return ans; } int main() {  ios::sync_with_stdio(false);  cin>>n>>m>>r; for(int i=1;i<=n;i++) {   cin>>b[i]; } int x,y; for(int i=1;i<n;i++) {   cin>>x>>y;   q[x].push_back(y);   q[y].push_back(x); } dfs(r,0); // dfs序 build(1, 1, n); int f; while(m--) {   cin>>f; if(f==1) {    cin>>x>>y; //   st[x], en[x]可找到子树的区间 zeng(1, st[x], en[x], 1, n, y); } else {    cin>>x;    cout<<he(1,st[x],en[x],1,n)<<endl; } } return 0; }