树上LCA3

题目描述

给你一棵树，以编号为 $1$ 的节点为根；

回答 $m$ 组询问，每组询问有两个数 $x, y (x\neq y)$, 你需要求出 $x, y$ 的最近公共祖先。

输入格式

第一行五个数$n, m, A, B, C(0\leq A, B, C\leq 2^{32}-1)$。

接下来 $n-1$ 行，每行给出两个数 $x, y (x\neq y)$，表示 $x, y$ 之间有一条边。

为了防止输入过大，询问用下面代码生成。

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%d%u%u%u", &n, &m, &A, &B, &C);
    // 输入树边
    for (int i = 1; i <= m; i++) {
        unsigned int u = rng61() % n + 1, v = rng61() % n + 1;
        ans[i] = LCA(u, v);
    }
}

输出格式

假设第$i$组询问的答案是$ans_i$，输出$ans_i\times i$的异或和。

样例输入

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

样例输出

9

数据范围

对于所有数据，保证$1\leq n\leq 5\times 10^5, 1\leq x, y \leq n, x \neq y , m\leq 10^7$。