2025/3/20

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

int n, m, R, a[maxn], dfn[maxn], id[maxn], idx, sz[maxn];
long long tr[maxn<<2];
vector<int> g[maxn];

void push_up(int u) {
	tr[u] = tr[u<<1] + tr[u<<1|1];
}
void build(int l, int r, int u) {
	if (l == r) {
		tr[u] = a[id[l]];
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, u<<1);
	build(mid+1, r, u<<1|1);
	push_up(u);
}
void add(int p, long long x, int l, int r, int u) {
	if (l == r) {
		tr[u] += x;
		return;
	}
	int mid = (l + r) / 2;
	(p <= mid) ? add(p, x, l, mid, u<<1) : add(p, x, mid+1, r, u<<1|1);
	push_up(u);
}
long long query(int L, int R, int l, int r, int u) {
	if (L <= l && r <= R)
		return tr[u];
	long long res = 0;
	int mid = (l + r) / 2;
	if (L <= mid) res += query(L, R, l, mid, u<<1);
	if (R > mid) res += query(L, R, mid+1, r, u<<1|1);
	return res;
}

void dfs(int u, int p) {
	dfn[u] = ++idx;
	id[idx] = u;
	sz[u] = 1;
	for (auto v : g[u])
		if (v != p)
			dfs(v, u), sz[u] += sz[v];
}

int main() {
	scanf("%d%d%d", &n, &m, &R);
	for (int i = 1; i <= n; i++)
		scanf("%d", a+i);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(R, -1);
	build(1, n, 1);
	while (m--) {
		int op, a, x;
		scanf("%d%d", &op, &a);
		if (op == 1) {
			scanf("%d", &x);
			add(dfn[a], x, 1, n, 1);
		}
		else {
			printf("%lld\n", query(dfn[a], dfn[a] + sz[a] - 1, 1, n, 1));
		}
	}
	return 0;
}

2025/3/19

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

int n, m, R, dfn[maxn], idx, id[maxn], val[maxn], sz[maxn];
vector<int> g[maxn];

void dfs(int u, int p) {
	dfn[u] = ++idx;
	id[idx] = u;
	sz[u] = 1;
	for (auto v : g[u])
		if (v != p)
			dfs(v, u), sz[u] += sz[v];
}

long long tr[maxn<<2];
void push_up(int u) {
	tr[u] = tr[u<<1] + tr[u<<1|1];
}
void build(int l, int r, int u) {
	if (l == r) {
		tr[u] = val[id[l]];
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, u<<1);
	build(mid+1, r, u<<1|1);
	push_up(u);
}
void add(int p, long long x, int l, int r, int u) {
	if (l == r) {
		tr[u] += x;
		return;
	}
	int mid = (l + r) / 2;
	(p <= mid) ? add(p, x, l, mid, u<<1) : add(p, x, mid+1, r, u<<1|1);
	push_up(u);
}
long long query(int L, int R, int l, int r, int u) {
	if (L <= l && r <= R)
		return tr[u];
	long long res = 0;
	int mid = (l + r) / 2;
	if (L <= mid) res += query(L, R, l, mid, u<<1);
	if (R > mid) res += query(L, R, mid+1, r, u<<1|1);
	return res;
}

int main() {
	scanf("%d%d%d", &n, &m, &R);
	for (int i = 1; i <= n; i++)
		scanf("%d", val+i);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(R, -1);
	build(1, n, 1);
	while (m--) {
		int op, a, x;
		scanf("%d%d", &op, &a);
		if (op == 1) {
			scanf("%d", &x);
			add(dfn[a], x, 1, n, 1);
		}
		else {
			printf("%lld\n", query(dfn[a], dfn[a] + sz[a] - 1, 1, n, 1));
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, rt, a[maxn], dfn[maxn], rev[maxn], sz[maxn], cnt;
vector<int> g[maxn];

void dfs(int u, int p) {
	dfn[u] = ++cnt;
	rev[cnt] = u;
	sz[u] = 1;
	for (auto v : g[u])
		if (v != p)
			dfs(v, u), sz[u] += sz[v];
}

// 线段树部分
long long tr[maxn<<2];
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
void push_up(int rt) {
	tr[rt] = tr[rt<<1] + tr[rt<<1|1];
}
void build(int l, int r, int rt) {
	if (l == r) {
		tr[rt] = a[ rev[l] ];
		return;
	}
	int mid = (l + r) / 2;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int p, int x, int l, int r, int rt) {
	if (l == r) {
		tr[rt] += x;
		return;
	}
	int mid = (l + r) / 2;
	(p <= mid) ? update(p, x, lson) : update(p, x, rson);
	push_up(rt);
}
long long query(int L, int R, int l, int r, int rt) {
	if (L <= l && r <= R) return tr[rt];
	long long res = 0;
	int mid = (l + r) /2;
	if (L <= mid) res += query(L, R, lson);
	if (R > mid) res += query(L, R, rson);
	return res;
}

int main() {
	scanf("%d%d%d", &n, &m, &rt);
	for (int i = 1; i <= n; i++)
		scanf("%d", a+i);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(rt, -1);
	build(1, n, 1);
	while (m--) {
		int op, u, x;
		scanf("%d%d", &op, &u);
		if (op == 1) {
			scanf("%d", &x);
			update(dfn[u], x, 1, n, 1);
		}
		else 
			printf("%lld\n", query(dfn[u], dfn[u] + sz[u] - 1, 1, n, 1));
	}
	return 0;
}