牛客小白月赛24 I 求和

题目地址：

https://ac.nowcoder.com/acm/contest/5158/I

基本思路：

来晚了,随便挑了一题I写,由于自己过于***树状数组写错了,所以没在比赛结束前交上去。
这题总体来说还是比较裸的,我们求一下dfs序,然后用树状数组维护子树的和就是了。
关于dfs序的具体内容的大家可以百度学习，这里简单介绍一下就是记录每个节点在dfs过程中进出栈的位置,两者中间的范围就是这个节点的子树即一个线性区间,我们知道了这一点就能将树形结构转化为线性结构,然后用数据结构类似树状数组去维护它就是了。
dfs序的一般求法：

int tot = 0,l[maxn],r[maxn];
void dfs(int u,int p,int d) {
  l[u] = ++tot;//进栈时间;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p)continue;
    dfs(to, u, d + 1);
  }
  r[u] = tot;//出栈时间;
}

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e6 + 10;
struct Edge{
    int to,next;
}edge[maxn << 1];
int cnt = 0,head[maxn];
void add_edge(int u,int v){
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
}
int tot = 0,l[maxn],r[maxn];
void dfs(int u,int p,int d) {
  l[u] = ++tot;//进栈时间;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p)continue;
    dfs(to, u, d + 1);
  }
  r[u] = tot;//出栈时间;
}
int n,m,k,w[maxn],d[maxn];
int lowbit(int x) {
  return x & (-x);
}
int sum(int x) {
  int res = 0;
  while (x) {
    res += d[x];
    x -= lowbit(x);
  }
  return res;
}
void update(int x,int v) {
  while (x <= cnt) {
    d[x] += v;
    x += lowbit(x);
  }
}
signed main() {
  n = read(), m = read(), k = read();
  rep(i, 1, n) w[i] = read();
  cnt = 0;
  mset(head, -1);
  rep(i, 1, n - 1) {
    int u, v;
    u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs(k, 0, 0);
  rep(i, 1, n) {
    update(l[i], w[i]);//初始一下数状数组;
  }
  while (m--) {
    int op;
    op = read();
    if (op == 1) {
      int a, x;
      a = read(), x = read();
      update(l[a], x);//更新;
    } else {
      int x;
      x = read();
      int ans = sum(r[x]) - sum(l[x] - 1); // 这段即是x的子树的和;
      cout << ans << '\n';
    }
  }
  return 0;
}