#O1046. 树上路径异或和

树上路径异或和

题目描述

给定一棵 nn 个点的树,点 ii 有点权 aia_i。回答 qq 次询问,每次给出 u,vu, v,求 uu 到 vv 的简单路径上所有点权的异或和(包含 uu 与 vv)。

题目类型

树上倍增、LCA

输入格式

第一行两个整数 n,qn, q。

接下来 n−1n-1 行,每行两个整数 u,vu, v,表示一条边。

下一行 nn 个整数 aia_i。

接下来 qq 行,每行两个整数 u,vu, v。

输出格式

共 qq 行,每行一个整数表示对应询问的异或和。

样例 #1

样例输入 #1

4 2
1 2
1 3
3 4
1 2 3 4
2 4
1 1

样例输出 #1

4
1

数据规模与约定

数据范围 说明
1≤n,q≤1051 \le n, q \le 10^5 点数与询问数
0≤ai≤1090 \le a_i \le 10^9 点权
  • 记 pxupx_u 为根到 uu(含 uu)的异或和,则答案为 pxu⊕pxv⊕alca(u,v)px_u \oplus px_v \oplus a_{\mathrm{lca}(u,v)}。