問題概要は以下の通りです。

根つき木が与えられます。以下のクエリを答えてください。

\(K\) 要素の頂点の部分集合 が与えられ、この集合について

• クエリ \(1\) : LCA から各頂点への距離の総和
• クエリ \(2\) : \(1\) 頂点取り除いた \(K-1\) 頂点における「 LCA から各頂点への距離の総和」の最小値

---

以降「 \(2\) 頂点の LCA をクエリ \(O(\log N)\) で求めるデータ構造」が既知であるとしましょう。

このデータ構造には様々なものが知られています。ゼロから書くのであればダブリングが簡単で、前計算 \(O(N \log N)\)、クエリ \(O(\log N)\) です。前計算 \(O(N)\)、クエリ \(O(1)\) まで高速化できますが、詳細はここでは省略します。

---

複数頂点の LCA

まず、複数頂点の LCA は \(2\) 頂点の LCA を繰り返しとることで求まります。

つまり \(S = \{v_1, v_2, \dots, v_K \}\) として、\(\operatorname{LCA}( S ) = \operatorname{LCA}(\operatorname{LCA}(\operatorname{LCA}(v_1, v_2), \ldots,v_{K-1}), v_K)\)

となります。

この証明は帰納法で簡単にできます。

クエリ \(1\) はこの頂点からの距離をそれぞれ求めればよいので、 \(O(K \log N)\) で解決できます。

---

クエリ \(2\) の解法

\(\operatorname{LCA}(S \setminus \{v_i\})\) の求め方を考えてみましょう。先程と同様の議論から

\(\operatorname{LCA}(S \setminus \{v_i\}) = \operatorname{LCA}(\operatorname{LCA}(\{v_1, \dots, v_{i-1}\}), \operatorname{LCA}(\{v_{i+1}, \dots, v_K\}) )\) であることを踏まえると、

すべての \(i\) について

• \(\operatorname{LCA}(\{v_1, \dots, v_{i-1}\})\)
• \( \operatorname{LCA}(\{v_{i+1}, \dots, v_K\})\)

が求まっていればよいです。これは、prefix と suffix それぞれについて LCA を求めればよいということであり、明らかに可能です。

---

問題は、LCA からの距離の総和（以降 \(\operatorname{dis}(S)\) とします）です。\(S\) の分割 \(S_1, S_2\) に対して \(l = \operatorname{LCA}(S), l_1 = \operatorname{LCA}(S_1), l_2 = \operatorname{LCA}(S_2)\) とすると

• \(\operatorname{dis}(S) = \operatorname{dis}(S_1) + \operatorname{dis}(S_2) + (l - l_1)|S_1| + (l-l_2)|S_2| \) となるはずですから、\(\operatorname{dis}, \operatorname{LCA}, |S|\)の情報をもつことで同様に prefix, suffix に対してすべての値を管理できます。

---

実装例

import sys
input = sys.stdin.readline

n, q = map(int, input().split())

log = n.bit_length()
up = [[-1] * n for _ in range(log)]
dep = [0] * n

p = list(map(int, input().split()))
for v in range(1, n):
    up[0][v] = p[v - 1] - 1
    dep[v] = dep[up[0][v]] + 1

for k in range(1, log):
    for v in range(n):
        p = up[k - 1][v]
        if p != -1:
            up[k][v] = up[k - 1][p]


def lca(u, v):
    if dep[u] < dep[v]:
        u, v = v, u
    d = dep[u] - dep[v]

    for k in range(log):
        if d >> k & 1:
            u = up[k][u]
    
    if u == v: return u

    for k in range(log - 1, -1, -1):
        if up[k][u] != up[k][v]:
            u = up[k][u]
            v = up[k][v]

    return up[0][u]


def merge(a, b):
    ans1, l1, s1 = a
    ans2, l2, s2 = b

    if s1 == 0: return b
    if s2 == 0: return a

    l = lca(l1, l2)
    ans = ans1 + ans2
    ans += (dep[l1] - dep[l]) * s1
    ans += (dep[l2] - dep[l]) * s2

    return ans, l, s1 + s2


for _ in range(q):
    a = list(map(int, input().split()))
    k = a[0]
    v = [x - 1 for x in a[1:]]

    pre = [(0, -1, 0)] * (k + 1)
    suf = [(0, -1, 0)] * (k + 1)

    for i in range(k):
        pre[i + 1] = merge(pre[i], (0, v[i], 1))
    for i in range(k - 1, -1, -1):
        suf[i] = merge((0, v[i], 1), suf[i + 1])

    ans1 = pre[k][0]
    if k == 1:
        print(ans1, -1)
        continue

    ans2 = 10**30
    for i in range(k):
        ans2 = min(ans2, merge(pre[i], suf[i + 1])[0])
    print(ans1, ans2)