P12393 「RiOI-6」flos

 即使是像萝卜这样不起眼的小木头，也有被人喜欢的日子呢！ 帽子的表白真是突如其来，小萝卜拼尽全力才战胜了自己上扬的嘴角，没有在上课划水的时候笑出来。 今年的 2.14，终于！可以！两个人过了！

帽子要摘一些小萝卜最喜欢的花装点礼物。 小萝卜最喜欢的花长在一棵根为 $1$ 的树上，其中每个节点都有一朵花。当帽子从点 $u$ 开始摘花时，花的芳香度 $w_v$ 定义为 $\operatorname{dis}(u,v)$，也即 $u$ 到 $v$ 的最短距离。帽子只能摘下一朵花。 帽子只有 $t$ 秒的时间。具体的，他从 $u$ 开始沿着边移动，当他向上爬一条边（即**远离根**）时消耗 $1$ 单位时间，向下滑一条边（即**接近根**）时不消耗时间，全过程中剩余时间不能少于 $0$。 小萝卜有 $q$ 个问题，每次形如：帽子从点 $x_i$ 出发，有 $t_i$ 时间，摘的花的最大芳香度是多少。各个询问相互独立。 特别的，有时候小萝卜会在帽子摘完花后才会问下一个问题，所以在一些测试点中你需要强制在线。

第一行两个正整数 $n,q,d$，表示树的节点个数、询问个数、与是否强制在线。 接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示树上 $u_i,v_i$ 之间有一条边。 接下来 $q$ 行，每行两个非负整数 $x_i,t_i$，表示一组询问。特别的，若 $d=1$，设上一组询问的答案为 $ans$（第一组询问为 $0$），你需要将 $x_i,t_i$ 异或上 $ans$ 得到真实询问。

$q$ 行每行一个非负整数，表示每个询问的答案。

#### 【样例解释】 对于样例 $1$，三个询问分别如下： - 从 $1$ 出发，体力值为 $2$。此时能摘下的其中一朵芳香度最大的花是 $4$，芳香度为 $2$。帽子可以向上爬 $2$ 条边到达 $4$。 - 从 $1$ 出发，体力值为 $4$。此时能摘下的其中一朵芳香度最大的花是 $5$，芳香度为 $3$。帽子可以向上爬 $3$ 条边到达 $5$。 - 从 $2$ 出发，体力值为 $2$。此时能摘下的其中一朵芳香度最大的花是 $4$，芳香度为 $3$。帽子可以先向下滑一条边到 $1$，再向上爬 $2$ 条边到达 $4$。 对于样例 $2$，暂时不能给你一个明确的答复。 #### 【数据范围】 **本题开启捆绑测试。** |子任务|分数|$n,q\le$|$d=$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$1$|$20$|$10^3$|$0$|| |$2$|$10$|$2\times10^5$|$0$|$\forall i,u_i+1=v_i$| |$3$|$20$|$2\times10^5$|$0$|$\forall i,t_i=n$| |$4$|$20$|$2\times10^5$|$0$|| |$5$|$30$|$2\times10^5$|$1$|| 对于 $100\%$ 的数据，$1\le n,q\le 2\times10^5,d\in\{0,1\},1\le x_i\le n,0\le t_i\le n$。