题目描述

Y 岛风景美丽宜人，气候温和，物产丰富。

Y 岛上有 $N$ 个城市（编号 $1,2,\dots,N$），有 $N-1$ 条城市间的道路连接着它们。

每一条道路都连接某两个城市。

幸运的是，小可可通过这些道路可以走遍 Y 岛的所有城市。

神奇的是，乘车经过每条道路所需要的费用都是一样的。

小可可，小卡卡和小 YY 经常想聚会，每次聚会，他们都会选择一个城市，使得 3 个人到达这个城市的总费用最小。

由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。

他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

输入格式

第一行两个正整数，$N$ 和 $M$，分别表示城市个数和聚会次数。

后面有 $N-1$ 行，每行用两个正整数 $A$ 和 $B$ 表示编号为 $A$ 和编号为 $B$ 的城市之间有一条路。

再后面有 $M$ 行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小 YY 所在的城市编号。

输出格式

一共有 $M$ 行，每行两个数 $Pos$ 和 $Cost$，用一个空格隔开，表示第 $i$ 次聚会的地点选择在编号为 $Pos$ 的城市，总共的费用是经过 $Cost$ 条道路所花费的费用。

样例

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

5 2
2 5
4 1
6 0

样例解释

树结构

$N=6$，边： 1-2, 2-3, 2-4, 4-5, 5-6 树形：

    1
    |
    2
   / \
  3   4
      |
      5
      |
      6

第一次聚会

小可可在城市 4，小卡卡在城市 5，小 YY 在城市 6。

我们需要找一个城市 $x$，使得 $dist(4,x) + dist(5,x) + dist(6,x)$ 最小。

• 如果选城市 4：距离 = 0+1+2=3
• 城市 5：1+0+1=2
• 城市 6：2+1+0=3
• 城市 2：2+3+4=9
• 城市 1：3+4+5=12
• 城市 3：3+4+5=12

最小总距离为 2，选城市 5，输出 5 2。

第二次聚会

城市 6, 3, 1

计算：

• 城市 1：5+2+0=7
• 城市 2：4+1+1=6
• 城市 3：4+0+2=6
• 城市 4：3+2+3=8
• 城市 5：2+3+4=9
• 城市 6：0+3+5=8

最小总距离为 6，对应城市 2 或 3。输出 2 5？为什么是 2 5？Cost 应该是总距离，输出 2 5 表示选城市 2，总距离 5？但计算得 6。可能我算错了。

重新计算： 城市 6 到各点距离：6→1:5, 6→2:4, 6→3:5, 6→4:3, 6→5:2, 6→6:0 城市 3 到各点：3→1:2, 3→2:1, 3→3:0, 3→4:2, 3→5:3, 3→6:5 城市 1 到各点：1→1:0, 1→2:1, 1→3:2, 1→4:2, 1→5:3, 1→6:5

总和：

• 城市1：5+2+0=7
• 城市2：4+1+1=6
• 城市3：5+0+2=7
• 城市4：3+2+2=7
• 城市5：2+3+3=8
• 城市6：0+5+5=10

最小是 6，城市 2，输出 2 5？不对，Cost 应该是总距离，应该是 6。但样例输出 2 5，说明 Cost 不是总距离，而是总道路数（总费用）？题目说“总共的费用是经过 Cost 条道路所花费的费用”，一条道路费用为 1，总费用就是总距离。但这里总距离是 6，输出 5，矛盾。

检查样例输出：

5 2
2 5
4 1
6 0

第二次输出 2 5，总距离应该是 6，但输出 5。可能我距离算错了。

计算城市 2 的总距离：

• 从 6 到 2：路径 6-5-4-2，距离 3？前面我算成 4 了，重新算： 树：6-5-4-2，所以 6 到 2 距离 3。
• 从 3 到 2：距离 1。
• 从 1 到 2：距离 1。 总和 = 3+1+1=5，正确！所以总费用是 5。

因此，样例输出正确。

第三次聚会

城市 2, 4, 4 有两个人在同一城市 4。

最优聚会点选 4，总距离 = dist(2,4)+0+0 = 1，输出 4 1。

第四次聚会

三人都在城市 6，选城市 6，总距离 0，输出 6 0。

数据范围

• $N \le 500000$
• $M \le 500000$

算法分析

这是一个树上的最近公共祖先（LCA） 问题。

对于三个点 $a,b,c$，要找一点 $x$ 使得 $dist(a,x) + dist(b,x) + dist(c,x)$ 最小。

结论：这个点 $x$ 一定是 $a,b,c$ 两两 LCA 中深度最大的那个点，或者是 $a,b,c$ 中某个点。

具体来说，设 $lca_{ab} = LCA(a,b)$, $lca_{bc} = LCA(b,c)$, $lca_{ac} = LCA(a,c)$。 令 $p$ 为这三个 LCA 中深度最大的那个，则 $x = p$ 就是最优聚会点。

另一种等价表述：$x$ 是 $a,b,c$ 两两路径的交点，也就是树上唯一的一个点，使得 $a,b,c$ 到该点的距离和最小。

证明

设 $d(u,v)$ 表示 $u$ 到 $v$ 的距离。 总距离 $D = d(a,x) + d(b,x) + d(c,x)$。

由树上距离公式：$d(a,x) = depth(a) + depth(x) - 2 \times depth(lca(a,x))$。

可以推导出 $D = depth(a)+depth(b)+depth(c) + 3 \times depth(x) - 2 \times [depth(lca(a,x)) + depth(lca(b,x)) + depth(lca(c,x))]$。

要使 $D$ 最小，相当于最大化 $depth(lca(a,x)) + depth(lca(b,x)) + depth(lca(c,x))$。

当 $x$ 是三个 LCA 中深度最大的那个时，上式最大。

计算总距离

设 $p =$ 深度最大的 LCA（即 $lca_{ab}, lca_{bc}, lca_{ac}$ 中深度最大的）。 则总距离 $D = d(a,b) + d(b,c) + d(a,c)$ 的一半？实际上，可以推导出：

$$D = d(a,p) + d(b,p) + d(c,p)$$

并且有：

$$d(a,b) = d(a,p) + d(b,p)$$

同理：

$$d(b,c) = d(b,p) + d(c,p)$$ $$d(a,c) = d(a,p) + d(c,p)$$

将三式相加得：

$$d(a,b) + d(b,c) + d(a,c) = 2 \times (d(a,p) + d(b,p) + d(c,p))$$

因此：

$$D = \frac{d(a,b) + d(b,c) + d(a,c)}{2}$$

所以，我们只需要计算两两之间的距离，除以 2 就是总费用。

而聚会点 $x$ 就是 $p$。

算法步骤

1. 读入树，预处理 LCA（使用倍增法或 Tarjan 离线算法）。
2. 对于每次查询 $(a,b,c)$：
   • 计算 $lca_{ab} = LCA(a,b)$, $lca_{bc} = LCA(b,c)$, $lca_{ac} = LCA(a,c)$。
   • 求出深度最大的 LCA，记为 $p$。
   • 计算 $d(a,b) = depth(a) + depth(b) - 2 \times depth(lca_{ab})$，同理 $d(b,c)$, $d(a,c)$。
   • 总费用 $Cost = (d(a,b) + d(b,c) + d(a,c)) / 2$。
   • 输出 $p$ 和 $Cost$。

复杂度

• 预处理 LCA：$O(N \log N)$。
• 每次查询 $O(\log N)$。
• 总复杂度 $O(N \log N + M \log N)$，对于 $N,M \le 500000$ 可以接受。

实现细节

• 使用倍增法求 LCA：预处理每个节点的 $2^k$ 级祖先和深度。
• 注意深度从 0 开始还是从 1 开始。
• 注意整数除法，总费用一定是整数（因为两两距离之和是偶数）。

样例验证

对于第一次查询 (4,5,6)：

• $lca(4,5)=4$, depth=2（假设根为1，depth(1)=0）
• $lca(5,6)=5$, depth=3
• $lca(4,6)=4$, depth=2 深度最大的是 $p=5$。 计算距离： $d(4,5)=1$, $d(5,6)=1$, $d(4,6)=2$。 总和 = 4，除以 2 得 2。 输出 5 2，正确。

第二次查询 (6,3,1)：

• $lca(6,3)=2$, depth=1
• $lca(3,1)=1$, depth=0
• $lca(6,1)=1$, depth=0 深度最大 $p=2$。 距离： $d(6,3)=?$ 计算深度：depth(6)=5, depth(3)=2, lca=2 depth=1 → $d=5+2-2=5$。 $d(3,1)=2+0-0=2$。 $d(6,1)=5+0-0=5$。 总和 12，除以 2 得 6？但样例输出 Cost=5，矛盾。

重新计算深度： 设根为 1，depth(1)=0, depth(2)=1, depth(3)=2, depth(4)=2, depth(5)=3, depth(6)=4。 $d(6,3) = depth(6)+depth(3)-2*depth(lca(6,3)) = 4+2-2*1=4$。 $d(3,1)=2+0-0=2$。 $d(6,1)=4+0-0=4$。 总和 10，除以 2 得 5，正确。所以 Cost=5，输出 2 5。

第三次查询 (2,4,4)：$p=4$，总距离 = $d(2,4)+0+0=1$，输出 4 1。

第四次查询 (6,6,6)：$p=6$，总距离 0，输出 6 0。

总结

本题关键结论：三个点的最优聚会点是两两 LCA 中深度最大的那个，总距离为两两距离之和的一半。利用 LCA 快速计算即可。