English · Original
Chinese · Translation
Formal · Original
Misha and Grisha are funny boys, so they like to use new underground. The underground has _n_ stations connected with _n_ - 1 routes so that each route connects two stations, and it is possible to reach every station from any other.
The boys decided to have fun and came up with a plan. Namely, in some day in the morning Misha will ride the underground from station _s_ to station _f_ by the shortest path, and will draw with aerosol an ugly text "Misha was here" on every station he will pass through (including _s_ and _f_). After that on the same day at evening Grisha will ride from station _t_ to station _f_ by the shortest path and will count stations with Misha's text. After that at night the underground workers will wash the texts out, because the underground should be clean.
The boys have already chosen three stations _a_, _b_ and _c_ for each of several following days, one of them should be station _s_ on that day, another should be station _f_, and the remaining should be station _t_. They became interested how they should choose these stations _s_, _f_, _t_ so that the number Grisha will count is as large as possible. They asked you for help.
## Input
The first line contains two integers _n_ and _q_ (2 ≤ _n_ ≤ 105, 1 ≤ _q_ ≤ 105) — the number of stations and the number of days.
The second line contains _n_ - 1 integers _p_2, _p_3, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_). The integer _p__i_ means that there is a route between stations _p__i_ and _i_. It is guaranteed that it's possible to reach every station from any other.
The next _q_ lines contains three integers _a_, _b_ and _c_ each (1 ≤ _a_, _b_, _c_ ≤ _n_) — the ids of stations chosen by boys for some day. Note that some of these ids could be same.
## Output
Print _q_ lines. In the _i_\-th of these lines print the maximum possible number Grisha can get counting when the stations _s_, _t_ and _f_ are chosen optimally from the three stations on the _i_\-th day.
[samples]
## Note
In the first example on the first day if _s_ = 1, _f_ = 2, _t_ = 3, Misha would go on the route 1 2, and Grisha would go on the route 3 1 2. He would see the text at the stations 1 and 2. On the second day, if _s_ = 3, _f_ = 2, _t_ = 3, both boys would go on the route 3 1 2. Grisha would see the text at 3 stations.
In the second examle if _s_ = 1, _f_ = 3, _t_ = 2, Misha would go on the route 1 2 3, and Grisha would go on the route 2 3 and would see the text at both stations.
Misha 和 Grisha 是两个有趣的男孩，他们喜欢使用新的地铁系统。该地铁系统有 #cf_span[n] 个站点，通过 #cf_span[n - 1] 条线路连接，每条线路连接两个站点，且从任意站点都能到达其他任意站点。
这两个男孩决定玩个游戏，制定了一个计划：在某天早上，Misha 会从站点 #cf_span[s] 沿最短路径乘坐地铁到站点 #cf_span[f]，并在他经过的所有站点（包括 #cf_span[s] 和 #cf_span[f]）上用喷雾剂写下丑陋的文字 "Misha was here"。随后在同一天傍晚，Grisha 会从站点 #cf_span[t] 沿最短路径乘坐地铁到站点 #cf_span[f]，并统计他经过的站点中有多少个带有 Misha 的文字。到了夜间，地铁工作人员会清除这些文字，以保持地铁的清洁。
男孩们已经为接下来的若干天分别选定了三个站点 #cf_span[a]、#cf_span[b] 和 #cf_span[c]，每一天，这三个站点中有一个将作为 #cf_span[s]，另一个作为 #cf_span[f]，剩下的作为 #cf_span[t]。他们想知道如何选择 #cf_span[s]、#cf_span[f]、#cf_span[t]，才能使 Grisha 统计到的带文字的站点数量最大化。他们向你寻求帮助。
第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 105]，#cf_span[1 ≤ q ≤ 105]）——站点数量和天数。
第二行包含 #cf_span[n - 1] 个整数 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi ≤ n]）。整数 #cf_span[pi] 表示站点 #cf_span[pi] 和站点 #cf_span[i] 之间有一条线路。保证从任意站点都能到达其他任意站点。
接下来的 #cf_span[q] 行，每行包含三个整数 #cf_span[a]、#cf_span[b] 和 #cf_span[c]（#cf_span[1 ≤ a, b, c ≤ n]）——男孩们为某一天选定的站点编号。注意，这些编号中可能有重复。
请输出 #cf_span[q] 行。在第 #cf_span[i] 行，输出在第 #cf_span[i] 天，从给定的三个站点中最优选择 #cf_span[s]、#cf_span[t] 和 #cf_span[f] 时，Grisha 能统计到的最大站点数。
在第一个例子中，第一天若 #cf_span[s] = #cf_span[1]，#cf_span[f] = #cf_span[2]，#cf_span[t] = #cf_span[3]，Misha 将沿路线 #cf_span[1] #cf_span[2] 行进，Grisha 将沿路线 #cf_span[3] #cf_span[1] #cf_span[2] 行进，他将在站点 #cf_span[1] 和 #cf_span[2] 上看到文字。第二天，若 #cf_span[s] = #cf_span[3]，#cf_span[f] = #cf_span[2]，#cf_span[t] = #cf_span[3]，两个男孩都将沿路线 #cf_span[3] #cf_span[1] #cf_span[2] 行进，Grisha 将在 #cf_span[3] 个站点上看到文字。
在第二个例子中，若 #cf_span[s] = #cf_span[1]，#cf_span[f] = #cf_span[3]，#cf_span[t] = #cf_span[2]，Misha 将沿路线 #cf_span[1] #cf_span[2] #cf_span[3] 行进，Grisha 将沿路线 #cf_span[2] #cf_span[3] 行进，并在两个站点上都看到文字。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 105]，#cf_span[1 ≤ q ≤ 105]）——站点数量和天数。第二行包含 #cf_span[n - 1] 个整数 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi ≤ n]）。整数 #cf_span[pi] 表示站点 #cf_span[pi] 和站点 #cf_span[i] 之间有一条线路。保证从任意站点都能到达其他任意站点。接下来的 #cf_span[q] 行，每行包含三个整数 #cf_span[a]、#cf_span[b] 和 #cf_span[c]（#cf_span[1 ≤ a, b, c ≤ n]）——男孩们为某一天选定的站点编号。注意，这些编号中可能有重复。
## Output
请输出 #cf_span[q] 行。在第 #cf_span[i] 行，输出在第 #cf_span[i] 天，从给定的三个站点中最优选择 #cf_span[s]、#cf_span[t] 和 #cf_span[f] 时，Grisha 能统计到的最大站点数。
[samples]
## Note
在第一个例子中，第一天若 #cf_span[s] = #cf_span[1]，#cf_span[f] = #cf_span[2]，#cf_span[t] = #cf_span[3]，Misha 将沿路线 #cf_span[1] #cf_span[2] 行进，Grisha 将沿路线 #cf_span[3] #cf_span[1] #cf_span[2] 行进，他将在站点 #cf_span[1] 和 #cf_span[2] 上看到文字。第二天，若 #cf_span[s] = #cf_span[3]，#cf_span[f] = #cf_span[2]，#cf_span[t] = #cf_span[3]，两个男孩都将沿路线 #cf_span[3] #cf_span[1] #cf_span[2] 行进，Grisha 将在 #cf_span[3] 个站点上看到文字。在第二个例子中，若 #cf_span[s] = #cf_span[1]，#cf_span[f] = #cf_span[3]，#cf_span[t] = #cf_span[2]，Misha 将沿路线 #cf_span[1] #cf_span[2] #cf_span[3] 行进，Grisha 将沿路线 #cf_span[2] #cf_span[3] 行进，并在两个站点上都看到文字。
**Definitions**
Let $ T = (V, E) $ be a tree with $ n $ nodes (stations) and $ n-1 $ edges (routes).
Let $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ T $.
Let $ P(u, v) $ denote the set of nodes on the unique simple path from $ u $ to $ v $ (inclusive).
For a query $ (a, b, c) $, assign $ s, f, t \in \{a, b, c\} $ as a permutation such that:
- $ s $: Misha’s start
- $ f $: Misha’s and Grisha’s destination
- $ t $: Grisha’s start
**Constraints**
1. $ 2 \le n \le 10^5 $
2. $ 1 \le q \le 10^5 $
3. For each query, $ a, b, c \in V $, not necessarily distinct.
**Objective**
For each query $ (a, b, c) $, maximize the number of stations visited by **both** Misha and Grisha:
$$
\max_{\text{permutation } (s,f,t) \text{ of } (a,b,c)} \left| P(s, f) \cap P(t, f) \right|
$$
That is, find the permutation of $ \{a,b,c\} $ to $ (s,f,t) $ that maximizes the size of the intersection of the two paths: Misha’s path from $ s $ to $ f $, and Grisha’s path from $ t $ to $ f $.
API Response (JSON)
{
"problem": {
"name": "D. Misha, Grisha and Underground",
"description": {
"content": "Misha and Grisha are funny boys, so they like to use new underground. The underground has _n_ stations connected with _n_ - 1 routes so that each route connects two stations, and it is possible to rea",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF832D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Misha and Grisha are funny boys, so they like to use new underground. The underground has _n_ stations connected with _n_ - 1 routes so that each route connects two stations, and it is possible to rea...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Misha 和 Grisha 是两个有趣的男孩，他们喜欢使用新的地铁系统。该地铁系统有 #cf_span[n] 个站点，通过 #cf_span[n - 1] 条线路连接，每条线路连接两个站点，且从任意站点都能到达其他任意站点。\n\n这两个男孩决定玩个游戏，制定了一个计划：在某天早上，Misha 会从站点 #cf_span[s] 沿最短路径乘坐地铁到站点 #cf_span[f]，并在他经过的所有站点（...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T = (V, E) $ be a tree with $ n $ nodes (stations) and $ n-1 $ edges (routes). \nLet $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v...",
"is_translate": false,
"language": "Formal"
}
]
}