U622285 【模板】DFS 序求 LCA
题目背景
>**注意：**
>- **本题极其卡常，请开启 O2 优化，选择 C++14(GCC 9) 语言，并使用快读，否则不保证能否通过。**
>- **此题为 DFS 序求 LCA 模版题，请不要用树剖进行无意义的卡常。**
[~~无耻宣传~~](https://www.cnblogs.com/lyas145/p/18778784)（看过的请无视）
之前的数据造小了，现已更正数据。
鉴于本题过于卡常，本题时限开大到 2.5s。
题目描述
给你一棵有 $n$ 个节点的树，其根节点编号为 $rt$。
有 $q$ 次询问，对于每一次询问，请你求出两个节点的 LCA。
### 数据范围
对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le q\le 10^7$，$1\le a,b\le n,1\le seed
输入格式
第 $1$ 行，两个正整数 $n,rt$，分别表示节点个数和根节点的编号。
第 $2\sim n$ 行，每行两个正整数 $a,b$，表示节点 $a,b$ 之间有一条直接相连的边。
第 $n+1$ 行，两个正整数 $q,seed$，分别表示询问次数和一个参数。
为了避免大量的输入，请采用下面的方式生成数据（C++）：
```cpp
typedef unsigned int uint;
uint seed,lt;
uint get_node() {
seed^=seed5;
seed^=seed*lt+1145;
return seed%n+1;
}
int main() {
...
q=read();seed=read();
while (q--) {
int x=get_node(),y=get_node();
...
}
}
```
其中 $lt$ 表示上一次询问所得的答案，如果是第一次询问，则为 $0$；`read()` 是快读函数。
输出格式
为了避免大量的输出，设第 $i$ 次询问的答案是 $lca_i$，那么最终输出一行一个整数 $ans=\oplus_{i=1}^q(i\times lca_i)$。
说明/提示
【样例解释 #1】
每组询问分别为
```
6 5
2 6
3 1
6 6
6 4
6 2
1 2
3 1
```
对于每次询问，答案分别为
```
5
2
5
6
5
2
2
5
```
计算后可得最终答案 $37$。