P17417 【MX-X31-T7】「FAOI-R14」Hello & Bye, Days（加强版）

>on this lonely day > >为逆光的诀别干杯 > >或许 我只是一个傀儡 > >在必然结局前被迫落泪 >

**原题见 [P17411](https://www.luogu.com.cn/problem/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$。

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

### 样例解释 树是一条链： $$ 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