解题思路
先把整棵树固定以节点 1 为根，预处理出任意两点的最近公共祖先（LCA）。
对于一次查询给定 (r,u,v)，要求的是：如果把整棵树改成以 r 为根时，u 和 v 的最近公共祖先是谁。
设：
- a=LCA(u,v)
P4717.第3题-动态换根的最近公共祖先
题目内容
在多元宇宙的中心，存在着一个名为“时空枢纽”的巨大网络。
这个网络由 n 个时空节点组成，它们通过稳定的因果律路径连接，构成了一棵宏伟的宇宙树。
通常，整个网络以创世节点（节点 1）为根进行校准。
然而，来自“混沌象限”的观察者们拥有改变宇宙视界的能力。
他们可以任意指定一个时空节点作为临时的“观测奇点”，从而使整个宇宙树的因果流向以该节点为根重新定向。
作为时空枢纽的守护者，你必须能够在这种动态的重构中，迅速定位任意两个节点在新的因果结构下的最近共同起源。
给定一个由 n 个节点构成的树。你需要处理 q 次查询。对于每次查询，给定三个节点 (r,u,v)。
你需要回答：如果将节点 r 作为整棵树的根，那么节点 u 和 v 的最近公共祖先是哪个节点？
【名词解释】
树：指这样的一张图，其由 n 个节点和 n−1 条边构成，其上的任意两个点都连通，且不存在环。
最近公共祖先：在一棵有根树中，节点 u 和 v 的最近公共祖先指同时位于“根到 u 的路径”和“根到 v 的路径”上的节点中，距离根节点最远的一个。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=2∗105) 代表数据组数，每组测试数据描述如下：
第一行输入两个整数 n,q(1<=n,q<=2∗105)，分别代表节点数和查询数。
此后 n−1 行，第 i 行输入两个整数 xi,yi(1<=xi,yi<=n,xi!=yi)，表示树上第 i 条边连接节点 xi 和 yi。
此后 q 行，第 i 行输入三个整数 ri,ui,vi(1<=ri,ui,vi<=n)，代表第 i 次查询。
除此之外，保证单个测试文件的 n 之和、q 之和均不超过 2∗105。
输出描述
对于每组测试数据，输出 q 行，第 i 行输出一个整数，代表第 i 次查询的答案。
样例1
输入
1
7 5
1 2
1 3
2 4
2 5
3 6
3 7
1 4 7
4 1 7
2 4 5
5 1 2
6 4 7
输出
1
1
2
2
3
说明
对于第一组测试数据，树的结构如下：
1
/
2 3
/ \ /
4 5 6 7
对于第一次查询，将节点 1 作为根：
从节点 4 到根 1 的路径是 4−>2−>1。
从节点 7 到根 1 的路径是 7−>3−>1。
两条路径在节点 1 处汇合，因此 1 是它们的最近公共祖先。输出 1。
对于第二次查询，将节点 4 作为根：
从节点 1 到根 4 的路径是 1−>2−>4。
从节点 7 到根 4 的路径是 7−>3−>1−>2−>4。
在这个新的结构中，节点 1 位于节点 7 到根 4 的路径上，因此 1 是 7 的祖先。输出 1。
