时间限制2s，内存限制1G

\\n

题目背景

\\n

有两棵树小 A 和小 B，小 A 发育不良，小 B 发育的很好。

\\n

为了追上小 B 的发育，小A 开始了魔改之路。

\\n

题目描述

\\n

小 A 有 $n$ 个节点，小 B 有 $m$ 个节点。每一个节点都有一种颜色。小 A 和小 B 都以一号节点为根。

\\n

为了追赶小 B，小 A 进行了 $q$ 次发育操作。

\\n

对于每一次操作先读入一个整数 $P$ 表示操作类型。

\\n

若 $P=1$，表示一次询问，那么接下来读入四个整数 $P_1,P_2,P_3,P_4$。

\\n

我们令 $lt$ 为上一次询问的答案，那么令 $D_1=P_3\\\\oplus lt,D_2=P_4\\\\oplus lt$，$lt$ 初始时为 $0$。

\\n

小 A 希望你能回答出小 A 的 $P_1$ 子树内离 $P_1$ 距离不超过 $D_1$ 和小 B 的 $P_2$ 子树内离 $P_2$ 距离不超过 $D_2$ 的节点中一共有多少种不同的颜色。

\\n

若 $P=2$，表示小 A 对自己进行了一次魔改发育，接下来读入两个整数 $S_1,S_2$ 表示小 A 将自己的 $S_1$ 节点的颜色魔改为了 $S_2$。

\\n

输入格式

\\n

第一行读入三个整数 $n,m,q$。

\\n

接下来读入 $n-1$ 行，每行两个正整数 $u,v$，表示有一条边连接小 A 的 $u$ 和 $v$。

\\n

然后读入 $m-1$ 行，每行两个正整数 $u,v$，表示有一条边连接小 B 的 $u$ 和 $v$。

\\n

紧接着读入 $n$ 行，每行一个正整数 $v_1$，第 $i$ 行表示小 A 的第 $i$ 号节点的颜色。

\\n

还需要读入 $m$ 行，每行一个正整数 $v_2$，第 $i$ 行表示小 B 的第 $i$ 号节点的颜色。

\\n

最后再读入 $q$ 个询问，询问格式见题目描述。

\\n

输出格式

\\n

对于每一个询问单独输出一行，每行一个整数表示答案。

\\n

样例数据

\\n

样例输入

\\n

统计

递交统计

[集训队互测 2022day1]树上的孤独

信息

状态

开发

支持

关于

登录