#O1046. 树上路径异或和
树上路径异或和
题目描述
给定一棵 个点的树,点 有点权 。回答 次询问,每次给出 ,求 到 的简单路径上所有点权的异或和(包含 与 )。
题目类型
树上倍增、LCA
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示一条边。
下一行 个整数 。
接下来 行,每行两个整数 。
输出格式
共 行,每行一个整数表示对应询问的异或和。
样例 #1
样例输入 #1
4 2
1 2
1 3
3 4
1 2 3 4
2 4
1 1
样例输出 #1
4
1
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数与询问数 | |
| 点权 |
- 记 为根到 (含 )的异或和,则答案为 。