牛客小白月赛24 I 求和 题解

Solution

比较经典的题型了吧, 我的做法是dfs序 + 树状数组
因为题目要求我们做到单点修改, 区间求和的一个操作
显然树状数组能够满足要求
那么问题便转化为如何把树上问题转化为简单的区间问题
考虑到每一个子树在dfs序下一定是连续的

我们可以保存它的编号最小点和编号最大点, 用来表示它的子树
比如, 对于 2 这个节点, 我们保存 2 和 4 表示以 2 为根这棵子树
剩下的就是很模板的树状数组区间求和, 单点更新了
具体看下代码吧

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int T[N];
int lowbit(int x){
  return x & (-x);
}
void update(int x, int add){
  while(x < N){
    T[x] += add;
    x += lowbit(x);
  }
}
ll query(int x){
  ll res = 0;
  while(x){
    res += T[x];
    x -= lowbit(x);
  }
  return res;
}
struct Edge{
  int v, nextz;
}edge[N << 1];
int tot, head[N];
void init(){
  memset(head, -1, sizeof(head));
}
void addedge(int u, int v){
  edge[tot].v = v;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
int l[N], r[N];
int cnt = 0;
int a[N];
void dfs(int u, int par){
  l[u] = ++cnt;
  for(int i = head[u]; ~i; i = edge[i].nextz){
    int v = edge[i].v;
    if(v == par) continue;
    dfs(v, u);
  }
  r[u] = cnt;
}
int main(){
  init();
  int n, m, root;
  cin >> n >> m >> root;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    addedge(u, v);
    addedge(v, u);
  }
  dfs(root, 0);
  for(int i = 1; i <= n; i++) update(l[i], a[i]);
  while(m--){
    int op;
    cin >> op;
    int x, y;
    if(op == 1){
      cin >> x >> y;
      update(l[x], y);
    }
    else {
      cin >> x;
      cout << query(r[x]) - query(l[x] - 1) << "\n";
    }
  }
  return 0;
}