#P2633. Count on a tree

    ID: 1640 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>线段树最近公共祖先LCA主席树可持久化

Count on a tree

题目描述

给定一棵 nn 个节点的树,每个点有一个权值。有 mm 个询问,每次给你 u,v,ku,v,k,你需要回答 u xor lastu \text{ xor last}vv 这两个节点间第 kk 小的点权。

其中 last\text{last} 是上一个询问的答案,定义其初始为 00,即第一个询问的 uu 是明文。

输入格式

第一行两个整数 n,mn,m

第二行有 nn 个整数,其中第 ii 个整数表示点 ii 的权值。

后面 n1n-1 行每行两个整数 x,yx,y,表示点 xx 到点 yy 有一条边。

最后 mm 行每行两个整数 u,v,ku,v,k,表示一组询问。

输出格式

mm 行,每行一个正整数表示每个询问的答案。

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2
2
8
9
105
7

提示

【数据范围】
对于 100%100\% 的数据,1n,m1051\le n,m \le 10^5,点权在 [1,2311][1, 2 ^ {31} - 1] 之间。

暴力自重。。。

来源:bzoj2588 Spoj10628.

本题数据为洛谷自造数据,使用 CYaRon 耗时 5 分钟完成数据制作。