#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <ctime>
#include <random>
#include <string>

using namespace std;

const int INF = 0x3f3f3f3f;
const int tag_p = 114514;

inline int read()
{
	int w = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		w = (w << 1) + (w << 3) + (ch ^ 48);
		ch = getchar();
	}
	return w * f;
}

inline void write(int x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

const int maxn = 3e4 + 5;

int n, q;
int val[maxn];
vector<int> G[maxn];

int sz[maxn], dep[maxn], f[maxn], hson[maxn];
void dfs1(int u, int fa, int depth)
{
	dep[u] = depth;
	sz[u] = 1;
	int max_son = -1;
	for (int v : G[u])
	{
		if (v == fa) continue;
		f[v] = u;
		dfs1(v, u, depth + 1);
		sz[u] += sz[v];

		if (max_son < sz[v])
		{
			max_son = sz[v];
			hson[u] = v;
		}
	}
}
int top[maxn], dfn[maxn], nval[maxn], cnt;
void dfs2(int u, int fa)
{
	top[u] = fa, dfn[u] = ++cnt, nval[cnt] = val[u];
	if (hson[u] == 0) return;
	dfs2(hson[u], fa);
	for (int v : G[u])
	{
		if (v == hson[u] || v == f[u]) continue;
		dfs2(v, v);
	}
}

struct node
{
	int l, r;
	int sum, maxx;
} tr[maxn << 2];
int ls(int p)
{
	return p << 1;
}
int rs(int p)
{
	return p << 1 | 1;
}
void pushup(int p)
{
	tr[p].maxx = max(tr[ls(p)].maxx, tr[rs(p)].maxx);
	tr[p].sum = tr[ls(p)].sum + tr[rs(p)].sum;
}
void build(int p, int l, int r)
{
	tr[p].l = l, tr[p].r = r;
	if (l == r)
	{
		tr[p].maxx = tr[p].sum = nval[l];
		return;
	}
	int mid = l + r >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	pushup(p);
}
void modify(int p, int pos, int k)
{
	if (tr[p].l == pos && tr[p].r == pos)
	{
		tr[p].maxx = k;
		tr[p].sum =  k;
		return;
	}
	int mid = tr[p].l + tr[p].r >> 1;
	if (mid >= pos) modify(ls(p), pos, k);
	else modify(rs(p), pos, k);
	pushup(p);
}
int query_max(int p, int l, int r)
{
	if (l <= tr[p].l && tr[p].r <= r) return tr[p].maxx;
	int mid = tr[p].l + tr[p].r >> 1;
	int maxx = -INF;
	if (mid >= l) maxx = max(maxx, query_max(ls(p), l, r));
	if (mid < r) maxx = max(maxx, query_max(rs(p), l, r));
	return maxx;
}
int query_sum(int p, int l, int r)
{
	if (l <= tr[p].l && tr[p].r <= r)
	{
		return tr[p].sum;
	}
	int mid = tr[p].l + tr[p].r >> 1, sum = 0;
	if (mid >= l) sum += query_sum(ls(p), l, r);
	if (mid < r) sum += query_sum(rs(p), l, r);
	return sum;
}

void modify_point(int x, int k)
{
	modify(1, dfn[x], k);
}
int query_path_max(int u, int v)
{
	int maxx = -INF;
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		maxx = max(maxx, query_max(1, dfn[top[u]], dfn[u]));
		u = f[top[u]];
	}
	if (dep[u] < dep[v]) swap(u, v);
	maxx = max(maxx, query_max(1, dfn[v], dfn[u]));
	return maxx;
}
int query_path_sum(int u, int v)
{
	int res = 0;
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		res += query_sum(1, dfn[top[u]], dfn[u]);
		u = f[top[u]];
	}
	if (dep[u] < dep[v]) swap(u, v);
	res += query_max(1, dfn[v], dfn[u]);
	return res;
}
string opt;
int u, v, t;
int main()
{
	n = read();
	for (int i = 1, u, v; i < n; ++i)
	{
		u = read(), v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i)
	{
		val[i] = read();
	}

	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, 1, n);
	for (int i = 1; i <= n; ++i)
	{
		cout << f[i] << " ";
	}
	cout << endl;
//	for (int i = 1; i <= 10; ++i)
//	{
//		cout << tr[i].maxx << " " << tr[i].sum << endl;
//	}
	q = read();
	while (q--)
	{
		cin >> opt;
		if (opt == "CHANGE")
		{
			u = read(), t = read();
			modify_point(u, t);
		}
		else if (opt == "QMAX")
		{
			u = read(), v = read();
			write(query_path_max(u, v));
			puts("");
		}
		else
		{
			u = read(), v = read();
			write(query_path_sum(u, v));
			puts("");
		}
	}
	return 0;
}