解题思路

先把整棵树固定以节点 $1$ 为根，预处理出任意两点的最近公共祖先（$LCA$）。

对于一次查询给定 $(r,u,v)$，要求的是：如果把整棵树改成以 $r$ 为根时，$u$ 和 $v$ 的最近公共祖先是谁。

设：

• $a=LCA(u,v)$

题目内容

在多元宇宙的中心，存在着一个名为“时空枢纽”的巨大网络。

这个网络由 $n$ 个时空节点组成，它们通过稳定的因果律路径连接，构成了一棵宏伟的宇宙树。

通常，整个网络以创世节点（节点 $1$）为根进行校准。

然而，来自“混沌象限”的观察者们拥有改变宇宙视界的能力。

他们可以任意指定一个时空节点作为临时的“观测奇点”，从而使整个宇宙树的因果流向以该节点为根重新定向。

作为时空枢纽的守护者，你必须能够在这种动态的重构中，迅速定位任意两个节点在新的因果结构下的最近共同起源。

给定一个由 $n$ 个节点构成的树。你需要处理 $q$ 次查询。对于每次查询，给定三个节点 ($r, u, v$)。

你需要回答：如果将节点 $r$ 作为整棵树的根，那么节点 $u$ 和 $v$ 的最近公共祖先是哪个节点？

【名词解释】

树：指这样的一张图，其由 $n$ 个节点和 $n-1$ 条边构成，其上的任意两个点都连通，且不存在环。

最近公共祖先：在一棵有根树中，节点 $u$ 和 $v$ 的最近公共祖先指同时位于“根到 $u$ 的路径”和“根到 $v$ 的路径”上的节点中，距离根节点最远的一个。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T (1 <= T <= 2 * 10^5)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n, q (1 <= n, q <= 2 * 10^5)$，分别代表节点数和查询数。

此后 $n-1$ 行，第 $i$ 行输入两个整数 $x_i, y_i (1 <= x_i, y_i <= n, x_i != y_i)$，表示树上第 $i$ 条边连接节点 $x_i$ 和 $y_i$。

此后 $q$ 行，第 $i$ 行输入三个整数 $r_i, u_i, v_i (1 <= r_i, u_i, v_i <= n)$，代表第 $i$ 次查询。

除此之外，保证单个测试文件的 $n$ 之和、$q$ 之和均不超过 $2 * 10^5$。

输出描述

对于每组测试数据，输出 $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$。