莫队学习笔记

提莫队长算法

莫队是一种离线数据结构，解决区间问题的数据结构，主要的思想是通过对区间离线下来，排序减少左右端点指针的移动次数，从而达到优雅的暴力的目的

当我们看到区间问题无法用线段树等常规数据结构很难维护时，不妨考虑莫队

算法流程大概就是：

对询问离线，然后排序

移动左右端点处理询问

普通莫队

算法本身很简单，所以我们通过例题讲解

对询问分块，块长 $\sqrt{n}$

把询问按左端点所在块排序，在一个块内的按右端点排序，当区间移动计算贡献是 $O(1)$ 时，整体算法复杂度 $O(n \sqrt{n})$

超 🐔 基础

P3901 数列找不同

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots , a_n$ ，每次询问 $[l, r]$ 的区间内 $a_l, a_l+1, \dots, a_r$ 是否互不相同

莫队入门题，开一个桶记录当前区间每一个数字的出现次数，然后在统计只出现一次的数的个数，如果这个这个次数等于区间长度就 Yes ，否则 No

code

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,q,a[MAXN];
int size,ans[MAXN];
struct node
{
    int l,r,num;
    friend bool operator < (node x,node y)
    {
        if(x.l /size != y.l /size)
            return x.l/size < y.l/size;
        else
            return x.r < y.r;
    }
}que[MAXN];
int L,R,cnt,t[MAXN];
void add(int x)
{
    if(!t[a[x]])
    cnt++;
    t[a[x]]++;
}
void del(int x)
{
    if(t[a[x]]==1)
    cnt--;
    t[a[x]]--;
}

int main()
{
    scanf("%d%d", &n, &m);
    size = pow(n, 0.5);
    for(int i = 1; i <= n; i++)    
    scanf("%d", &a[i]);
    
    for(int i = 1; i <= m; i++)
    {
        que[i].num = i;
        scanf("%d%d", &que[i].l, &que[i].r);
    }
    sort(que + 1, que + 1 + m);
    L = 1; R = 0;
    for(int i = 1; i <= m; i++)
    {
        int l = que[i].l , r = que[i].r;
        while(L > l) add(--L);
        while(R < r) add(++R);
        while(L < l) del(L++);
        while(R > r) del(R--);
        if(cnt == (r - l + 1))
        ans[que[i].num] = 1;
    }
    for(int i = 1; i <= m; i++)
    {
        if(ans[i]) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

注意处理端点移动时的顺序，有很多正确的写法，但一般保证先加后删

SP3267 DQUERY - D-query

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots , a_n$ ，每次询问 $[l, r]$ 的区间内有多少不同的数字

和上一道题双倍经验，只要输出只出现一次的数的个数就行辣

还是基础

P2709 小B的询问

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ ，值域为 $k$ ，每次给定一个区间 $[l, r]$ ，求：
$\sum\limits_{i = 1}^k cnt_i^2$
$cnt_i$ 指数字 $i$ 在 $[l, r]$ 区间内出现的次数

稍微需要一点思考，没什么好说的

(a+b)^2 = a^2 + 2ab + b^2 \\ (c_i + 1)^2 - (c_i)^2 = 2 \times c_i + 1

code

void add(int pos)
{
    cnt[a[pos]]++;
    ANS += 2*cnt[a[pos]]-1;
}
void del(int pos)
{
    cnt[a[pos]]--;
    ANS -= 2*cnt[a[pos]]+1;
}

P1494 小 Z 的袜子

给定一个长度为 $n$ 的序列，每一个元素对应一个颜色，每次询问区间 $[l, r]$ 内随机选出两个元素，它颜色相同的概率

首先，选出一🐑颜色的方案数

​ \sum\limits_{i = l}^{r} cnt[i]∗(cnt[i]−1)，cnt[i]>=2

总方案数

C_{2}^{len}

然后考虑区间移动造成的影响

code

$Ans$ 表示选出相同颜色的方案数

void add(int pos)
{
    ANS -= cnt[a[pos]]*(cnt[a[pos]]-1);
    cnt[a[pos]]++;
    ANS += cnt[a[pos]]*(cnt[a[pos]]-1);
}

void del(int pos)
{
    ANS -= cnt[a[pos]]*(cnt[a[pos]]-1);
    cnt[a[pos]]--;
    ANS += cnt[a[pos]]*(cnt[a[pos]]-1);
}

乱七八糟

P4462 CQOI2018异或序列

给定一个长度为 $n$ 序列和 $k$ ，每次查询区间 $[l, r]$ 内有多少子区间异或和等于 $k$

因为要处理区间的异或和，考虑前缀和，这样 $\oplus_l^r = \oplus_1^r \land \oplus_1^{l-1}$

那么每加入一个数 $x$ ，与它对答案有贡献的数的前缀和 $y$ ，一定是 $x \oplus y = k$ ，所以找出这样的数有几个就好了

code

$sum$ 表示异或和

void add(int pos)
{
    ANS += cnt[sum[pos]^k];
    cnt[sum[pos]]++;
}
void del(int pos)
{
    cnt[sum[pos]]--;
    ANS -= cnt[sum[pos]^k];
}

双倍经验 CF617E

P3730

这里用到了莫队常常会一起用的一个东西，值域分块。常常用来优化查询的复杂度

统计答案时，如果一个一个枚举的话，肯定不行，所以对桶也分个块，一块一块的枚举来找到答案在哪个块。

Code

cnt 表示经典桶 cntt 表示对出现次数cnt开的桶。cnbt 是对 cnt 的值域分块开的桶

void add(int x)
{
	cntt[cnt[x]]--;
	cnbt[bel[cnt[x]]]--;
	cnt[x]++;
	cnbt[bel[cnt[x]]]++;
	cntt[cnt[x]]++;
}
void del(int x)
{
	cntt[cnt[x]]--;
	cnbt[bel[cnt[x]]]--;
	cnt[x]--;
	cnbt[bel[cnt[x]]]++;
	cntt[cnt[x]]++;
}
int get_ans(int k)
{
	int i;
	for (i = 1; i <= cntb; i++)
	{
		if (k - cnbt[i] <= 0) break;
		k -= cnbt[i];
	}
	if (i == cntb + 1) return -1;
	for (int j = L[i]; j <= R[i]; j++)
	{
		if (k - cntt[j] <= 0) return j;
		k -= cntt[j];
	}
	return 114514;
}

同样可以莫队+值域分块的题 P4147

P4396 AHOI2013

同样可以值域分块，但是这里介绍多个 $log$ 的做法

经典桶，然后整俩值域树状数组分别维护两个答案。

Code

#include <bits/stdc++.h>
#define MAXN 100005

using namespace std;

int n, m, a[MAXN], SIZE;
#define bel(i) (i / SIZE + 1)

struct query
{
	int l, r, a, b, id;
}que[MAXN];

struct BIt
{
	int lim, t[MAXN];
	#define lowbit(i) (i & -i)
	void init(int x) {lim = x;}
	void add(int i, int val)
	{
		if (!i) return; while (i <= lim) t[i] += val, i += lowbit(i);
	}
	int query(int i, int res = 0)
	{
		while (i) res += t[i], i -= lowbit(i); return res;
	}

}t1, t2;

int cnt[MAXN];
void add(int pos)
{
	if (cnt[a[pos]] == 0) t2.add(a[pos], 1);
	cnt[a[pos]]++; t1.add(a[pos], 1);
}
void del(int pos)
{
	if (cnt[a[pos]] == 1) t2.add(a[pos], -1);
	cnt[a[pos]]--; t1.add(a[pos], -1);
}

int ans1[MAXN], ans2[MAXN];

int main()
{
	read(n, m); SIZE = sqrt(n); int mxz = 0;
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i <= m; i++)
	{
		int l, r, a, b; read(l, r, a, b);
		que[i] = {l, r, a - 1, b, i};
		mxz = max({mxz, a, b});
	}
	t1.init(mxz); t2.init(mxz);
	sort(que + 1, que + 1 + m, [&](query a, query b)
	{
		if (bel(a.l) != bel(b.l)) return a.l < b.l;
		return bel(a.l) & 1 ? a.r < b.r : a.r > b.r;
	});

	int L = 1, R = 0;
	for (int i = 1; i <= m; i++)
	{
		int l = que[i].l, r = que[i].r;
		while (L > l) add(--L);
		while (R < r) add(++R);
		while (L < l) del(L++);
		while (R > r) del(R--);
		ans1[que[i].id] = t1.query(que[i].b) - t1.query(que[i].a);
		ans2[que[i].id] = t2.query(que[i].b) - t2.query(que[i].a);
	}
	for (int i = 1; i <= m; i++)
	print(ans1[i], ' '), print(ans2[i], '\n');

	return 0;
}

tips

一个有点用的优化。

考虑我们正常排序的结果，右端点排了序大概是这样的。

这样子左端点到了新块之后，右端点大概会移动图中红色的距离

换一个方式排序，如果左端点是奇数，按右端点升序，右端点是偶数，按右端点降序。这样以后大概是这样的

有点时候优化还挺明显的，一般叫这个奇偶优化

带修莫队

我们知道一般离线算法是不能带修的，但是如果修改产生的影响可以方便删除的添加到答案中也不是不行
一般莫队的询问都有两维，带修莫队就多了一个按修改决定的时间维度，排序时把时间作为第三关键字排序即可

还有和普通莫队的不一样的就是，这次块长为 $n^{\frac{2}{3}}$ ，排序是先按左端点所在块排序，再按右端点所在块排序，最后按时间排序，至于为什么我不到啊

时间复杂度 $O(n^{\frac{5}{3}})$

P1903 数颜色

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots , a_n$ ，每次询问 $[l, r]$ 的区间内有多少不同的数字，单点修改

和 SP3267 相比，就是多了一个修改操作

考虑如何实现修改，实际上我们只要把原来位置数字的贡献删掉，再加入新数字产生的贡献就行辣还要考虑的就是我们排序时，时间是第三关键字，所以会出现修改完再修改回去的情况，如何实现这样一个回溯的过程呢，有一个巧妙的做法

code

for(int i = 1;i <= m;i++)
{
    char o;
    int a,b;
    scanf("%c %d %d", &o, &a, &b);
    if(o == 'Q')
    {
        cntq++;
        que[cntq].l = a;
        que[cntq].r = b;
        que[cntq].num = cntq;
        que[cntq].t = cntc;
    }
    else
    {
        cntc++;
        c[cntc].pos = a; c[cntc].val = b;
    }
}

void change(int now)
{
    if(c[now].pos >= L && c[now].pos <= R) //如果修改位置对答案有贡献
    {
        del(a[c[now].pos]); //删去原来贡献
        add(c[now].val);    //添加现在贡献
    }
    swap(c[now].val,a[c[now].pos]); //把现在的值和要修改的值交换，以便回溯
}

for(int i = 1;i <= cntq;i++)
{
    int l = que[i].l , r = que[i].r , t = que[i].t;
    while(L > l) add(a[--L]);
    while(R < r) add(a[++R]);
    while(L < l) del(a[L++]);
    while(R > r) del(a[R--]);
    while(T < t) change(++T); //修改时间维度
    while(T > t) change(T--); 
    ans[que[i].num] = ANS;
}

双倍经验 UVA12345

CF940F Machine Learning

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots , a_n$ ，每次询问 $[l, r]$ 区间数字出现次数的 $mex$ ，单点修改
$mex$ 指的是一些数字里没有出现的最小的自然数

和上面有道题一样，您也可以值域分块，但是这个题数据比较水。可以直接暴力求 $mex$

for(ANS = 1;cntt[ANS] > 0;ANS++); ans[que[i].num] = ANS;

还有就是记得离散化一下

回滚莫队

回滚莫队，只不删除或不添加的莫队比如说这道题

JOISC2014

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots , a_n$ ，每次询问 $[l, r]$ 区间数字最大的重要度。
定义一个数字 $x$ 的重要度为 $x \times cnt_x$

明显不能像普通莫队一样直接区间移动，因为删除一个数的贡献很难维护，所以考虑避免删除操作。

我们可以备份一个版本的答案，然后通过回溯到这个版本来实现删除

于是有了这样一个思路：

对询问分块，左端点一个块内按右端点排序，否则按左端点所在块排序
如果询问在一个块内，直接暴力，因为块长最多 $\sqrt{n}$ ，单次询问 $O(\sqrt n)$
每当左端点移动一个整块，就初始化 L 为块的左端点，R 为块的左端点减一，原理和普通莫队的 L = 1, R = 0 一样
我们询问保证了同一个块内的右端点单调增，所以不用删除右端点移动产生的贡献，但是左端点不一样，所以备份左端点答案，添加后回溯。也可以说创造一个工具人存档，用它去处理左端点的移动

code

int n, m, SIZE;
int a[MAXN], h[MAXN];

int bel[MAXN];
namespace BLOCK //分块预处理
{
	int cnt;	
	int L[MAXN], R[MAXN];
	void pre_block()
	{
		SIZE = sqrt(n); cnt = n / SIZE;
		for (int i = 1; i <= cnt; i++)
		{
			L[i] = R[i-1]+1;
			R[i] = i * SIZE;
		}
		if(R[cnt] < n)
		{
			L[cnt+1] = R[cnt]+1;
			R[cnt+1] = n; cnt++;
		}
		for (int i = 1; i <= cnt; i++)
		{
			for (int j = L[i]; j <= R[i]; j++)
			bel[j] = i;
		}
	}
	#define BK BLOCK
}

int L = 1, R = 0; ll Ans; ll ans[MAXN];
int cnt[MAXN], cut[MAXN];
// 一个维护区间移动，一个维护同一个块内的暴力

void pre_lsh()// 值域 1e9,经典离散化
{
	sort(h + 1, h + 1 + n);
	int len = unique(h+1, h+1+n) - h - 1;
	for (int i = 1; i <= n; i++)
	a[i] = lower_bound(h+1, h+1+len, a[i]) - h;
}

void add(int pos, ll &res)// 加贡献
{
	cnt[a[pos]]++;
	res = max(res, cnt[a[pos]] * 1LL * h[a[pos]]);
}

void del(int pos)// 删贡献
{
	cnt[a[pos]]--;
}

int main()
{
	n = read(); m = read();
	for (int i = 1; i <= n; i++)
		a[i] = h[i] = read();
	BK::pre_block(); pre_lsh();
	for (int i = 1; i <= m; i++)
	{
		q[i].l = read(); q[i].r = read();
		q[i].id = i;
	}

	sort(q + 1, q + 1 + m, cmp);

	int last = 0; // 上一个询问左端点所在块
	for (int i = 1; i <= m; i++)
	{
		int l = q[i].l, r = q[i].r;

		if (bel[l] == bel[r]) // 一个块内，直接暴力
		{
			for (int j = l; j <= r; j++)
			{
				cut[a[j]]++;
				ans[q[i].id] = max(ans[q[i].id], h[a[j]]*1LL*cut[a[j]]);
			}
			for (int j = l; j <= r; j++) cut[a[j]]--;
			continue;
		}
		if (bel[l] != last) // 到达新块，初始化
		{
			while(R > BK::R[bel[l]]) del(R--);
			while(L < BK::R[bel[l]]+1) del(L++);
			Ans = 0; last = bel[l];
		}

		while (R < r) add(++R, Ans); // 添加右端点
		int LL = L; ll res = Ans; // 备份答案，处理左端点的移动
		while (LL > l) add(--LL, res); 
		while (LL < L) del(LL++); // 删除左端点
		
		ans[q[i].id] = res;

	}

	for (int i = 1 ; i <= m; i++)
		printf("%lld\n", ans[i]);

	return 0;
}

树上莫队

这里介绍使用括号序的树上莫队

我们知道莫队和关键所在是区间端点的移动，所以得把数整到序列上去，考虑一棵树的括号序

这棵树的括号序是

1	3	5	5	7	7	6	6	3	4	8	8	4	2	2	1

可以发现的是每个节点都在括号序上出现了两次，而且它出现的两个位置之间是它的子树。

那么两个节点括号序之间可能会出现查询的节点的兄弟节点，而这些节点是不需要的。但是是 dfs 序，那么这些节点要么不会出现，要么出现恰好两次。而且两个节点之间括号序是不含有他们的 LCA 的

比如说我们要查询节点 7 和节点 4 之间，反映到括号序上就是 7 6 6 3 4 但实际上应该有 7 3 1 4 这些节点

缺少了它们的 LCA ，而且多了节点 6 ，发现像 6 这样多出来的节点一定会出现两次，不妨将计就计，可以打一个标记，第一次出现就加贡献，第二次出现就删贡献，然后再特判 LCA

还有就是如果询问的两个节点之一就是他们的 LCA 的话，括号序上是包含 LCA 的，特判一下

SP10707 Count on a tree II

给定 $n$ 个结点的树，每个结点有一种颜色。

$m$ 次询问，每次询问给出 $u,v$ ，回答 $u,v$ 之间的路径上的结点的不同颜色数。

纯纯滴板子题结合代码理解

Code

int n, m, SIZE;
int a[MAXN], b[MAXN];
int bel[MAXN];

struct query
{
	int l, r, u, v, id, lca;
}que[MAXM];

bool cmp(query a, query b)
{
	if (bel[a.l] != bel[b.l]) return bel[a.l] < bel[b.l];
	if (bel[a.l] % 2)
		return a.r < b.r;
	else return a.r > b.r;	
}

vector <int> e[MAXN];

int euler_cnt;
int euler[MAXN*2], in[MAXN], out[MAXN];
int siz[MAXN], dep[MAXN], fa[MAXN], top[MAXN], son[MAXN];

// dfs 整括号序，顺便树剖LCA
void dfs1(int u, int dad)
{
	euler[in[u] = ++euler_cnt] = u; // 括号序中第一次出现
	fa[u] = dad; siz[u] = 1; dep[u] = dep[dad] + 1;
	for (int v : e[u]) if (v != dad)
	{
		dfs1(v, u); siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
	}
	euler[out[u] = ++euler_cnt] = u; // 括号序中第二次出现
}

void dfs2(int u, int tup)
{
	top[u] = tup; if (son[u]) dfs2(son[u], tup);
	for (int v : e[u]) if (v != son[u] && v != fa[u])
	{
		dfs2(v, v);
	}
}

int LCA(int u, int v)
{
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

int L = 1, R = 0, Ans;
int cnt[MAXM];
int vis[MAXN]; // 记录第一次还是第二次

void add(int pos)
{
	cnt[a[pos]]++;
	if (cnt[a[pos]] == 1) Ans++;
}

void del(int pos)
{
	cnt[a[pos]]--;
	if (cnt[a[pos]] == 0) Ans--;
}

void change(int pos)
{
	int u = euler[pos];
	vis[u] ? del(u) : add(u);
	vis[u] ^= 1;
}

int ans[MAXM];

int main()
{
	read(n, m);
	for (int i = 1; i <= n; i++)
	{
		read(a[i]); b[i] = a[i];
	}
    // 离散化
	sort(b + 1, b + 1 + n);
	int len = unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; i++)
	a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
	for (int i = 1; i < n; i++)
	{
		int u, v; read(u, v);
		e[u].push_back(v); e[v].push_back(u);
	}
	dfs1(1, 0); dfs2(1, 1); SIZE = pow(euler_cnt, 0.5); // 括号序上莫队，注意块长
	for (int i = 1; i <=euler_cnt; i++) bel[i] = i / SIZE + 1;

	for (int i = 1; i <= m; i++)
	{
		int u, v; read(u, v);
		que[i].id = i;
		if (in[u] > in[v]) swap(u, v); // 先后顺序
		que[i].u = u; que[i].v = v;
        // 根据 LCA 分情况
		if (u == LCA(u, v))
		{
			que[i].l = in[u];
			que[i].r = in[v];
			que[i].lca = 0;
		}
		else
		{
			que[i].l = out[u];
			que[i].r = in[v];
			que[i].lca = LCA(u, v);
		}
	}
	sort(que+1, que+1+m, cmp);
	for (int i = 1; i <= m; i++)
	{
		int l = que[i].l, r = que[i].r;
		while (L > l) change(--L);
		while (L < l) change(L++);
		while (R < r) change(++R);
		while (R > r) change(R--);
        // 特判 LCA
		if (que[i].lca) change(in[que[i].lca]);
		ans[que[i].id] = Ans;
		if (que[i].lca) change(in[que[i].lca]);
	}
	for (int i = 1; i <= m; i++)
	printf("%d\n", ans[i]);

	return 0;
}

P4074 WC2013 糖果公园

糖果公园的结构十分奇特，形式化为一棵 $n$ 个节点的树，一共有 $m$ 种糖果，每个节点都有一种糖果 $C_i$

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

根据游客们的反馈打分，我们得到了糖果的美味指数，第 $i$ 种糖果的美味指数为 $V_i$ 。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 $i$ 次品尝某类糖果的新奇指数 $W_i$ 。如果一位游客第 $i$ 次品尝第 $j$ 种糖果，那么他的愉悦指数 $H$ 将会增加对应的美味指数与新奇指数的乘积，即 $V_j$ × $W_i$ 。这位游客游览公园的愉悦指数最终将是这些乘积的和。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

形式化一下，查询一条路径上的 $\sum\limits_{i}^{tot} v_i \times \sum\limits_{j}^{cnt_i}w_j$

$tot$ 表示路径上一共出现了几种颜色， $cnt_i$ 表示第 $i$ 种颜色出现了几次

树上带修莫队，当作板子吧

单点的贡献加减也很好维护

Code

int n, m, q, SIZE;
int a[MAXN];
int v[MAXN], w[MAXN], c[MAXN];

vector <int> e[MAXN];

int euler[MAXN * 2], euler_cnt;
int in[MAXN], out[MAXN];
int siz[MAXN], son[MAXN], dep[MAXN];
int top[MAXN], fa[MAXN];

void dfs1(int u, int dad)
{
	fa[u] = dad; dep[u] = dep[dad] + 1; siz[u] = 1;
	euler[in[u] = ++euler_cnt] = u;
	for (int v : e[u]) if (v != dad)
	{
		dfs1(v, u); siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
	}
	euler[out[u] = ++euler_cnt] = u;
}
void dfs2(int u, int tup)
{
	top[u] = tup; if(son[u]) dfs2(son[u], tup);
	for (int v : e[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
int LCA(int u, int v)
{
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

int cntq, cntc;
struct query { int l, r, u, v, lca, t, id; }que[MAXN];

struct modify { int pos, val; }mdf[MAXN];

bool cmp (query a, query b)
{
	if (a.l / SIZE != b.l / SIZE) return a.l / SIZE < b.l / SIZE;
	if (a.r / SIZE != b.r / SIZE) return a.r < b.r;
	return a.t < b.t;
}

int cnt[MAXN], vis[MAXN];
int L = 1, R = 0, T;
ll Ans, ans[MAXN];

void add(int pos) { Ans += 1LL * v[c[pos]] * w[++cnt[c[pos]]]; }

void del(int pos) { Ans -= 1LL * v[c[pos]] * w[cnt[c[pos]]--]; }

void work(int pos) { vis[pos] ? del(pos) : add(pos); vis[pos] ^= 1; }

void change(int T)
{
	int pos = mdf[T].pos;
	if (vis[pos]) { work(pos); swap(mdf[T].val, c[pos]); work(pos); }
	else swap(mdf[T].val, c[pos]);
}

int main()
{
	read(n, m, q);
	for (int i = 1; i <= m; i++) read(v[i]);
	for (int i = 1; i <= n; i++) read(w[i]);
	for (int i = 1; i < n; i++)
	{
		int u, v; scanf("%d%d", &u, &v);
		e[u].push_back(v); e[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) read(c[i]);
	dfs1(1, 0); dfs2(1, 1); SIZE = pow(euler_cnt, 0.66666667);

	for (int i = 1; i <= q; i++)
	{
		int op, x, y; read(op, x, y);
		if (op == 1)
		{
			cntq++; if (in[x] > in[y]) swap(x, y);
			int lca = LCA(x, y);
			if (x == lca) que[cntq] = { in[x], in[y], x, y, 0 , cntc, cntq};
			else que[cntq] = { out[x], in[y], x, y, lca, cntc, cntq};
		}
		else
		{
			mdf[++cntc] = {x, y}; 
		}
	}
	sort(que+1, que+1+cntq, cmp);
	for (int i = 1; i <= q; i++)
	{
		int l = que[i].l, r = que[i].r, t = que[i].t;
		while (L > l) work(euler[--L]);
		while (L < l) work(euler[L++]);
		while (R < r) work(euler[++R]);
		while (R > r) work(euler[R--]);
		while (T < t) change(++T);
		while (T > t) change(T--);
		if (que[i].lca) work(que[i].lca);
		ans[que[i].id] = Ans;
		if (que[i].lca) work(que[i].lca);
	}
	for (int i = 1; i <= cntq; i++) printf("%lld\n", ans[i]);

	return 0;
}