写的树上带修莫队。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 100001

inline void read(int &T) {
	int x = 0;
	bool f = 0;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = !f;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	T = f ? -x : x;
}

void write(long long x) {
	if (x < 0) putchar('-'), write(-x);
	else {
		if (x / 10) write(x / 10);
		putchar(x % 10 + '0');
	}
}

typedef long long ll;
ll ans[MAXN];
int n, m, s, sqrn, pthn, head[MAXN], a[MAXN], v[MAXN], w[MAXN], num[MAXN << 1], cnt[MAXN], vis[MAXN];
int c_, cc, cq, fir[MAXN], la[MAXN], pre[MAXN << 1], dep[MAXN], lg[MAXN], fa[MAXN][21];
struct change {
	int w, pos;
}c[MAXN];
struct query {
	int x, y, t, lca, id;
	friend bool operator < (query q1, query q2) {
		if (num[q1.x] != num[q2.x]) return num[q1.x] < num[q2.x];
		if (num[q1.y] != num[q2.y]) return num[q1.y] < num[q2.y];
		return q1.y < q2.y;
	}
}q[MAXN];
struct Edge {
	int next ,to;
}pth[MAXN << 1];

void add(int from, int to) {
	pth[++pthn].to = to, pth[pthn].next = head[from];
	head[from] = pthn;
}

void dfs(int u, int father) {
	fa[u][0] = father, dep[u] = dep[father] + 1;
	fir[u] = ++c_, pre[c_] = u;
	for (int i = head[u]; i; i = pth[i].next) {
		int x = pth[i].to;
		if (x != father) dfs(x, u);
	}
	la[u] = ++c_, pre[c_] = u;
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) std::swap(x, y);
	while (dep[x] > dep[y]) {
		x = fa[x][lg[dep[x] - dep[y]] - 1];
	}
	if (x == y) return x;
	for (int k = lg[dep[x]] - 1; k >= 0; --k) {
		if (fa[x][k] != fa[y][k]) {
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	return fa[x][0];
}

void work(int now, ll &ans) {
	if (vis[now]) {
		ans -= 1ll * w[cnt[a[now]]] * v[a[now]];
		--cnt[a[now]];
	}
	else {
		++cnt[a[now]];
		ans += 1ll * w[cnt[a[now]]] * v[a[now]];
	}
	vis[now] ^= 1;
}

bool okay(int nq, int node) {
	bool flag1 = (fir[node] >= q[nq].x && fir[node] <= q[nq].y && (la[node] < q[nq].x || la[node] > q[nq].y));
	bool flag2 = (la[node] >= q[nq].x && la[node] <= q[nq].y && (fir[node] < q[nq].x || fir[node] > q[nq].y));
	return (flag1 || flag2);
}

int main() {
	read(n), read(m), read(s), sqrn = pow(2 * n, 2.0 / 3.0);
	for (int i = 1; i <= 2 * n; ++i) num[i] = (i - 1) / sqrn + 1;
	for (int i = 1; i <= m; ++i) read(v[i]);
	for (int i = 1; i <= n; ++i) read(w[i]);
	for (int i = 1, u, v; i < n; ++i) {
		read(u), read(v);
		add(u, v), add(v, u);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; ++i) {
		lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
	}
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i <= n; ++i) {
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
	for (int i = 1; i <= n; ++i) read(a[i]);
	for (int i = 1, opt, x, y, f; i <= s; ++i) {
		read(opt), read(x), read(y);
		if (opt == 1) {
			f = lca(x, y), q[++cq].id = cq, q[cq].t = cc;
			if (fir[x] > fir[y]) std::swap(x, y);
			if (x == f) {
				q[cq].x = fir[x];
				q[cq].y = fir[y];
			}
			else {
				q[cq].x = la[x];
				q[cq].y = fir[y];
				q[cq].lca = f;
			}
		}
		else c[++cc].w = y, c[cc].pos = x;
	}
	std::sort(q + 1, q + cq + 1);
	int l = 1, r = 0, t = 0;
	ll now = 0;
	for (int i = 1; i <= cq; ++i) {
		//printf("%d %d\n", q[i].x, q[i].y);
		while (l > q[i].x) work(pre[--l], now);
		while (r < q[i].y) work(pre[++r], now);
		while (l < q[i].x) work(pre[l++], now);
		while (r > q[i].y) work(pre[r--], now);
		while (t < q[i].t) {
			++t;
			bool flag = okay(i, c[t].pos);
			if (flag) {
				work(c[t].pos, now);
				std::swap(c[t].w, a[c[t].pos]);
				work(c[t].pos, now);
			}
			else std::swap(a[c[t].pos], c[t].w);
		}
		while (t > q[i].t) {
			bool flag = okay(i, c[t].pos);
			if (flag) {
				work(c[t].pos, now);
				std::swap(a[c[t].pos], c[t].w);
				work(c[t].pos, now);
			}
			else std::swap(a[c[t].pos], c[t].w);
			--t;
		}
		if (q[i].lca) work(q[i].lca, now);
		ans[q[i].id] = now;
		if (q[i].lca) work(q[i].lca, now);
	}
	for (int i = 1; i <= cq; ++i) {
		write(ans[i]);
		puts("");
	}
	return 0;
}