#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int>e[N];
int n, dep[N], fa[N][21], m, root;

void dfs(int x, int f, int deep) {
	dep[x] = deep;
	fa[x][0] = f;
	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs(v, x, deep + 1);
	}
}

int lca(int x, int y) {
	if (dep[x] > dep[y])
		swap(x, y);
	//跳y
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]] >= dep[x])
			y = fa[y][j];
	}
	if (x == y)
		return x;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			x = fa[x][j];
			y = fa[y][j];
		}
	}
	return fa[x][0];
}

int main() {
	cin >> n >> m >> root;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(root, 0, 1);
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << '\n';
	}
	return 0;
}

/*
H[x]根节点到x路径中H的个数
G[x]根节点到x路径中G的个数
A~B是否有H   H[A]+H[B]-2*H[LCA(A,B)]+(LCA(A,B)=='H')>0
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, dep[N], fa[N][21], H[N], G[N];
string s;
vector<int>e[N];

void dfs(int x, int f, int deep) {
	G[x] = G[f] + (s[x - 1] == 'G');
	H[x] = H[f] + (s[x - 1] == 'H');
	fa[x][0] = f;
	dep[x] = deep;
	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs(v, x, deep + 1);
	}
}

int lca(int x, int y) {
	if (dep[x] > dep[y])
		swap(x, y);
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]] >= dep[x])
			y = fa[y][j];
	}
	if (x == y)
		return x;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			x = fa[x][j];
			y = fa[y][j];
		}
	}
	return fa[x][0];
}

int main() {
	cin >> n >> m;
	cin >> s;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0, 1);
	while (m--) {
		int x, y;
		char ch;
		cin >> x >> y >> ch;
		if (ch == 'H') {
			int LCA = lca(x, y);
			int res = H[x] + H[y] - 2 * H[LCA] + (s[LCA - 1] == 'H');
			if (res > 0)
				cout << 1;
			else
				cout << 0 ;
		} else {
			int LCA = lca(x, y);
			int res = G[x] + G[y] - 2 * G[LCA] + (s[LCA - 1] == 'G');
			if (res > 0)
				cout << 1 ;
			else
				cout << 0 ;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5, Mod = 998244353;
vector<int>e[N];
int n, dep[N][51], fa[N][21], m, root;
int sum[N][51];

void dfs(int x, int f, int deep) {
	dep[x][1] = deep;
	sum[x][1] = sum[f][1] + deep;
	for (int j = 2; j <= 50; j++) {
		dep[x][j] = dep[x][j - 1] * dep[x][1];
		dep[x][j] %= Mod;
		sum[x][j] = sum[f][j] + dep[x][j];
		sum[x][j] %= Mod;
	}
	fa[x][0] = f;
	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs(v, x, deep + 1);
	}
}

int lca(int x, int y) {
	if (dep[x][1] > dep[y][1])
		swap(x, y);
	//跳y
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]][1] >= dep[x][1])
			y = fa[y][j];
	}
	if (x == y)
		return x;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			x = fa[x][j];
			y = fa[y][j];
		}
	}
	return fa[x][0];
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	root = 1;
	memset(dep, -1, sizeof(dep));
	dfs(root, 0, 0);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, k;
		cin >> x >> y >> k;
		int LCA = lca(x, y);
		cout << (((sum[x][k] + sum[y][k]) % Mod + 2 * Mod - 2 * sum[LCA][k]) % Mod + dep[LCA][k]) % Mod << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int>e[N];
int n, dep[N], fa[N][21], m, root;
int w[N];

void dfs(int x, int f, int deep) {
	dep[x] = deep;
	fa[x][0] = f;
	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs(v, x, deep + 1);
	}
}

int lca(int x, int y) {
	if (dep[x] > dep[y])
		swap(x, y);
	//跳y
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]] >= dep[x])
			y = fa[y][j];
	}
	if (x == y)
		return x;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			x = fa[x][j];
			y = fa[y][j];
		}
	}
	return fa[x][0];
}

void dfs2(int x, int f) {
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs2(v, x);
		w[x] += w[v];
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	root = 1;
	dfs(root, 0, 1);
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		w[x]++;
		w[y]++;
		int LCA = lca(x, y);
		w[LCA]--;
		w[fa[LCA][0]]--;
	}
	dfs2(1, 0);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res = max(res, w[i]);
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, father[N];

struct node {
	int u, v, w;
} E[50005];

struct T {
	int v, w;
};
vector<T>e[N];
int fa[N][21], dep[N], g[N][21];

//g[i][j]从i开始往上数2^j个节点，边权的最大值
bool cmp(node a, node b) {
	return a.w > b.w;
}

int find(int x) {
	if (x == father[x])
		return x;
	else
		return father[x] = find(father[x]);
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	father[fx] = fy;
}

void dfs(int x, int f, int deep, int weight) {
	dep[x] = deep;
	fa[x][0] = f;
	g[x][0] = weight;
	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
		g[x][j] = min(g[x][j - 1], g[fa[x][j - 1]][j - 1]);
	}
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int w = e[x][i].w;
		if (v == f)
			continue;
		dfs(v, x, deep + 1, w);
	}
}

int lca(int x, int y) {
	int res = 1e9;
	if (dep[x] > dep[y])
		swap(x, y);
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]] >= dep[x])
			res = min(res, g[y][j]), y = fa[y][j];
	}
	if (x == y)
		return res;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			res = min(res, g[y][j]);
			y = fa[y][j];
			res = min(res, g[x][j]);
			x = fa[x][j];
		}
	}
	return min(res, min(g[x][0],g[y][0]));
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		father[i] = i;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		E[i] = {x, y, z};
	}
	sort(E + 1, E + m + 1, cmp);
	for (int i = 1; i <= m; i++) {
		int u = E[i].u, v = E[i].v, w = E[i].w;
		int fu = find(u), fv = find(v);
		if (fu != fv) {
			merge(u, v);
			e[u].push_back({v, w});
			e[v].push_back({u, w});
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!dep[i]) {
			dfs(i, 0, 1, 0);
		}
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		if (find(x) != find(y)) {
			cout << -1 << endl;
		} else {
			int res = lca(x, y);
			cout << res << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, root;
int a[N], id[N], w[N], cnt, tree[N], siz[N];
vector<int>e[N];

void dfs1(int x, int f) {
	id[x] = ++cnt;
	w[id[x]] = a[x];
	siz[x] = 1;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x);
		siz[x] += siz[v];
	}
}

int lobit(int x) {
	return x & -x;
}

void update(int x, int c) {
	for (int i = x; i <= n; i += lobit(i)) {
		tree[i] += c;
	}
}

int query(int x) {
	int res = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		res += tree[i];
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> root;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(root, 0);
	for (int i = 1; i <= n; i++) {
		update(id[i], w[id[i]]);
	}
	for (int i = 1; i <= m; i++) {
		int op, x, y;
		cin >> op >> x;
		if (op == 1) {
			cin >> y;
			update(id[x], y);
		} else {
			//x为根的子树根节点编号id[x],id[x]+siz[x]-1
			if (id[x] == 1)
				cout << query(id[x] + siz[x] - 1) << '\n';
			else
				cout << query(id[x] + siz[x] - 1) - query(id[x] - 1) << '\n';
		}
	}
	return 0;
}