CF832D Misha, Grisha and Underground

Misha 和 Grisha 是两个有趣的男孩，他们喜欢乘坐新开的地铁。地铁一共有 $n$ 个车站，通过 $n-1$ 条路线连接，每条路线连接两个站，并且任意两个站都可以互相到达。 他们决定玩一个有趣的游戏。一天早上，Misha 将从车站 $s$ 出发，沿最短路径到达车站 $f$，在途中经过的所有车站（包括 $s$ 和 $f$）上用喷雾写下丑陋的“ Misha was here ”涂鸦。当天晚上，Grisha 将从车站 $t$ 出发，沿最短路径到达车站 $f$，数一数沿途带有 Misha 涂鸦的车站数。当天深夜，地铁工作人员会把涂鸦彻底清理干净，以保持地铁卫生。 男孩们为接下来的几天分别选好了三座车站 $a$、$b$ 和 $c$。每天的三座车站中，一个作为 $s$，一个作为 $f$，另一个作为 $t$。他们好奇每次如何选择 $s$、$f$、$t$，才能让 Grisha 数到的带有 Misha 涂鸦的车站数最大。现在他们请求你帮忙计算。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 10^{5}$，$1 \le q \le 10^{5}$），分别表示车站数和询问天数。 第二行包含 $n-1$ 个整数 $p_2, p_3, ..., p_n$（$1 \le p_i \le n$）。其中 $p_i$ 表示存在一条线路连接车站 $p_i$ 和 $i$。保证任意两个车站可达。 接下来 $q$ 行，每行包含三个整数 $a, b, c$（$1 \le a, b, c \le n$），表示男孩们当天选定的三座车站编号。注意，这些编号可能相同。

输出 $q$ 行，每行一个整数，表示在第 $i$ 天中，当最优地选择 $s$、$f$、$t$ 后，Grisha 最多能数到多少个带有 Misha 涂鸦的车站。

在第一个样例的第一天，如果 $s=1$，$f=2$，$t=3$，Misha 将沿 $1$ 到 $2$ 的路线行进，Grisha 将沿 $3$ 到 $1$ 再到 $2$ 的路线行进。他将看到编号 $1$ 和 $2$ 两站上的涂鸦。在第二天，如果 $s=3$，$f=2$，$t=3$，两人都将沿 $3$ 到 $1$ 再到 $2$ 的路线行进。Grisha 将在 $3$ 个站都能看到涂鸦。 在第二个样例中，如果 $s=1$，$f=3$，$t=2$，Misha 将走 $1$ 到 $2$ 到 $3$，Grisha 将走 $2$ 到 $3$，他可以在两个站看到涂鸦。 由 ChatGPT 5 翻译