背景

on this lonely day

为逆光的诀别干杯

或许 我只是一个傀儡

在必然结局前被迫落泪

题目描述

原题见 P17411，但是被一些不希望通过的做法过掉了，因此带了个权，卡了一下空间和时间。

给定一棵 $n$ 个点的树，你需要维护关键点集合 $S$，初始时 $S$ 为空，定义 $\mathrm{dis}(x,y)$ 为 $x,y$ 在树上的距离，$d(x)=\min\limits_{y\in S}\mathrm{dis}(x,y)$。

每个点 $i$ 还有一个正整数权值 $w_i$。

接下来有 $q$ 次操作，第 $i$ 次操作有两种类型：

• 1 x，如果 $x$ 在 $S$ 中，从 $S$ 中删掉 $x$；否则向 $S$ 中加入 $x$。

• 2 x，输出 $\sum\limits_{i=1}^n[d(i)=\mathrm{dis}(x,i)]w_i$，保证这里 $x\in S$，即有多少个点 $i$ 满足 $x$ 是到其最近的关键点之一。

部分测试点需要你在线的回答询问。

输入格式

第一行三个整数 $n,q,t$，分别代表点数、操作次数，以及和强制在线有关的参数。

接下来 $n-1$ 行，每行一对整数 $x_i,y_i$，代表一条边。

接下来一行 $n$ 个整数 $w_1\cdots w_n$ 代表每个数的权值。

接下来 $q$ 行，每行两个整数 $op\space z$，其中 $op$ 代表了操作类型，$z$ 代表了加密前的信息，

令

$$x=z\mathbin{\operatorname{xor}}\mathrm{(lastans\times t)},$$

则 $x$ 为本次操作的真实点编号，其中 $\mathrm{lastans}$ 为上次询问的答案，初始时为 $0$。

保证：

• 解密后 $1\le x\le n$；
• 对于 2 操作，解密后的 $x\in S$；
• 每次操作执行完毕后，集合 $S$ 非空。

输入中的加密点编号 $z$ 可能为 $0$。

输出格式

若干行，每行代表一次询问的答案。

5 7 0
1 2
2 3
3 4
4 5
1 1 1 1 1
1 1
2 1
1 5
2 1
2 5
1 1
2 5

5
3
3
5

提示

样例解释

树是一条链：

$$1-2-3-4-5$$

• 加入关键点 $1$ 后，$S=\{1\}$。所有点的最近关键点都是 $1$，第一次询问输出 $5$。

• 加入关键点 $5$ 后，$S=\{1,5\}$：

  • 对关键点 $1$，满足条件的点为 $1,2,3$；
  • 对关键点 $5$，满足条件的点为 $3,4,5$。

点 $3$ 到两个关键点的距离均为 $2$，因此会被两个询问同时计入。

• 最后删除关键点 $1$，此时 $S=\{5\}$，所有点的最近关键点都是 $5$，所以输出 $5$。

数据规模

本题有子任务约束。

• 对于 $10\%$ 的数据，$n,q\leq 3000$。
• 对于 $40\%$ 的数据，$n,q\leq 5\times 10^4$。
• 对于另外 $10\%$ 的数据，树是一条链。
• 对于另外 $20\%$ 的数据，$t=0$。
• 对于 $100\%$ 的数据，$1\leq n,q\leq 2\times 10^5$，$1\leq x_i,y_i\leq n$，$t\in \{0,1\}$，$op\in \{1,2\}$，$0\leq z<2^{30},1\leq w_i\leq 10^3$。