Tree Queries (Codeforces 1904E)
Tags: Implement, trees

Those who don't work don't eat. Get the things you want with your own power. But believe, the earnest and serious people are the ones who have the last laugh... But even then, I won't give you a present.—Santa, Hayate no Gotoku!Since Hayate didn't get any Christmas presents from Santa, he is instead left solving a tree query problem.Hayate has a tree with $$$n$$$ nodes.Hayate now wants you to answer $$$q$$$ queries. Each query consists of a node $$$x$$$ and $$$k$$$ other additional nodes $$$a_1,a_2,\ldots,a_k$$$. These $$$k+1$$$ nodes are guaranteed to be all distinct.For each query, you must find the length of the longest simple path starting at node $$$x^\dagger$$$ after removing nodes $$$a_1,a_2,\ldots,a_k$$$ along with all edges connected to at least one of nodes $$$a_1,a_2,\ldots,a_k$$$.$$$^\dagger$$$ A simple path of length $$$k$$$ starting at node $$$x$$$ is a sequence of distinct nodes $$$x=u_0,u_1,\ldots,u_k$$$ such that there exists a edge between nodes $$$u_{i-1}$$$ and $$$u_i$$$ for all $$$1 \leq i \leq k$$$.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of nodes of the tree and the number of queries.The following $$$n - 1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — denoting an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.The following $$$q$$$ lines describe the queries. Each line contains the integers $$$x$$$, $$$k$$$ and $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq k < n$$$, $$$1 \leq a_i \leq n$$$) — the starting node, the number of removed nodes and the removed nodes.It is guaranteed that for each query, $$$x,a_1,a_2,\ldots,a_k$$$ are all distinct.It is guaranteed that the sum of $$$k$$$ over all queries will not exceed $$$2 \cdot 10^5$$$.

Output: For each query, output a single integer denoting the answer for that query.

Note: In the first example, the tree is as follows:   In the first query, no nodes are missing. The longest simple path starting from node $$$2$$$ is $$$2 \to 1 \to 3 \to 4$$$. Thus, the answer is $$$3$$$.In the third query, nodes $$$1$$$ and $$$6$$$ are missing and the tree is shown below. The longest simple path starting from node $$$2$$$ is $$$2 \to 5$$$. Thus, the answer is $$$1$$$.   

Sample Inputs:
7 7
1 2
1 3
3 4
2 5
2 6
6 7
2 0
2 1 1
2 2 1 6
3 1 4
3 1 1
5 0
5 2 1 6

4 4
1 2
1 3
2 4
2 1 3
3 1 4
2 1 4
2 3 1 3 4

Sample Outputs:
3
2
1
4
1
4
1

1
2
2
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph1(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def make_graph2(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def euler_tour():
    st = [1]
    now = list(s0)
    (t1, t2) = ([0] * (n + 1), [0] * (n + 1))
    (t1[1], t) = (1, 2)
    dist = [0] * (n + 1)
    parent = [-1] * (n + 1)
    while st:
        i = st[-1]
        if now[i] < s0[i + 1] and t1[G[now[i]]]:
            now[i] += 1
        if now[i] < s0[i + 1]:
            j = G[now[i]]
            now[i] += 1
            dist[j] = dist[i] + 1
            parent[j] = i
            t1[j] = t
            t += 1
            st.append(j)
        else:
            t2[i] = t
            t += 1
            st.pop()
    return (t1, t2, dist, parent)

def f(i):
    if not lazy[i]:
        return
    tree[i] += lazy[i]
    if i < l1:
        lazy[i << 1] += lazy[i]
        lazy[i << 1 ^ 1] += lazy[i]
    lazy[i] = 0
    return

def update(l, r, s):
    q = [1 << 40 ^ l1 - 1]
    for i in q:
        (j, l0, r0) = (i >> 40, i >> 20 & 1048575, i & 1048575)
        if l <= l0 and r0 <= r:
            if s:
                lazy[j] += s
            f(j)
            i += 1
            continue
        f(j)
        m0 = l0 + r0 >> 1
        if l <= m0 and l0 <= r:
            q.append(j << 1 << 40 ^ l0 << 20 ^ m0)
        if l <= r0 and m0 + 1 <= r:
            q.append((j << 1 ^ 1) << 40 ^ m0 + 1 << 20 ^ r0)
        i += 1
    for q0 in q[::-1]:
        i = q0 >> 40
        if i < l1:
            (j, k) = (i << 1, i << 1 ^ 1)
            f(j)
            f(k)
            tree[i] = max(tree[j], tree[k])
    return

def get_max(s, t):
    if not s <= t:
        return -inf
    update(s, t, 0)
    s += l1
    t += l1
    ans = -inf
    while s <= t:
        if s & 1:
            ans = max(ans, tree[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree[t])
            t -= 1
        t >>= 1
    return ans

def g(u, v):
    return 20 * u + v
(n, q) = map(int, input().split())
(G, s0) = make_graph1(n, n - 1)
(t1, t2, dist, parent) = euler_tour()
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
p = [t1[i] << 20 ^ i for i in range(1, n + 1)]
p = [i & 1048575 for i in sorted(p)]
dp = [-1] * (20 * (n + 1))
for i in range(1, n + 1):
    dp[g(i, 0)] = parent[i]
for i in p:
    k = parent[i]
    for j in range(1, 20):
        if k == -1:
            break
        k = dp[g(k, j - 1)]
        dp[g(i, j)] = k
a = []
s1 = [0] * (q + 1)
x = [0] * (2 * q)
for i in range(q):
    t = list(map(int, input().split()))
    (x[2 * i], x[2 * i + 1]) = (t[0], i)
    for j in t[2:]:
        a.append(j)
    s1[i + 1] = len(a)
(Q, s2) = make_graph2(n, q)
l1 = pow(2, (2 * n + 1).bit_length())
l2 = 2 * l1
inf = 1 << 30
(tree, lazy) = ([-inf] * l2, [0] * l2)
for i in range(1, n + 1):
    tree[t1[i] + l1] = dist[i]
    tree[t2[i] + l1] = dist[i]
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
st = [1]
now = list(s0)
ans = [0] * q
visit = [0] * (n + 1)
while st:
    i = st[-1]
    if not visit[i]:
        (li, ri) = (t1[i], t2[i])
        for u in range(s2[i], s2[i + 1]):
            (j, z) = (Q[u], [l1 - 1 << 1])
            (ll, rr) = (-inf, inf)
            for v in range(s1[j], s1[j + 1]):
                k = a[v]
                (lk, rk) = (t1[k], t2[k])
                if not lk < li < ri < rk:
                    z.append(lk << 1)
                    z.append(rk << 1 ^ 1)
                else:
                    d = dist[i] - dist[k] - 1
                    k = i
                    for l in range(20):
                        if not d:
                            break
                        if d & pow2[l]:
                            d ^= pow2[l]
                            k = dp[g(k, l)]
                    (lk, rk) = (t1[k], t2[k])
                    (ll, rr) = (max(ll, lk), min(rr, rk))
            (l0, c, ans0) = (1, 0, -inf)
            for v in sorted(z):
                if not c:
                    r0 = (v >> 1) - 1
                    ans0 = max(ans0, get_max(max(ll, l0), min(rr, r0)))
                if v & 1:
                    c += 1
                else:
                    c -= 1
                if not c:
                    l0 = (v >> 1) + 1
            ans0 += dist[i]
            ans[j] = ans0
        visit[i] = 1
    if now[i] < s0[i + 1] and visit[G[now[i]]]:
        now[i] += 1
    if now[i] < s0[i + 1]:
        j = G[now[i]]
        (lj, rj) = (t1[j], t2[j])
        update(lj, rj, -2)
        now[i] += 1
        st.append(j)
    else:
        j = i
        (lj, rj) = (t1[j], t2[j])
        update(lj, rj, 2)
        st.pop()
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph1(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def make_graph2(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def euler_tour():
    st = [1]
    now = list(s0)
    (t1, t2) = ([0] * (n + 1), [0] * (n + 1))
    (t1[1], t) = (1, 2)
    dist = [0] * (n + 1)
    parent = [-1] * (n + 1)
    while st:
        i = st[-1]
        if now[i] < s0[i + 1] and t1[G[now[i]]]:
            now[i] += 1
        if now[i] < s0[i + 1]:
            j = G[now[i]]
            now[i] += 1
            dist[j] = dist[i] + 1
            parent[j] = i
            t1[j] = t
            t += 1
            st.append(j)
        else:
            t2[i] = t
            t += 1
            st.pop()
    return (t1, t2, dist, parent)

def f(i):
    if not lazy[i]:
        return
    tree[i] += lazy[i]
    if i < l1:
        lazy[i << 1] += lazy[i]
        lazy[i << 1 ^ 1] += lazy[i]
    lazy[i] = 0
    return

def update(l, r, s):
    q = [1 << 40 ^ l1 - 1]
    for i in q:
        (j, l0, r0) = (i >> 40, i >> 20 & 1048575, i & 1048575)
        if l <= l0 and r0 <= r:
            if s:
                lazy[j] += s
            f(j)
            i += 1
            continue
        f(j)
        m0 = l0 + r0 >> 1
        if l <= m0 and l0 <= r:
            q.append(j << 1 << 40 ^ l0 << 20 ^ m0)
        if l <= r0 and m0 + 1 <= r:
            q.append((j << 1 ^ 1) << 40 ^ m0 + 1 << 20 ^ r0)
        i += 1
    for q0 in q[::-1]:
        i = q0 >> 40
        if i < l1:
            (j, k) = (i << 1, i << 1 ^ 1)
            f(j)
            f(k)
            tree[i] = max(tree[j], tree[k])
    return

def get_max(s, t):
    if not s <= t:
        return -inf
    update(s, t, 0)
    s += l1
    t += l1
    ans = -inf
    while s <= t:
        if s & 1:
            ans = max(ans, tree[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree[t])
            t -= 1
        t >>= 1
    return ans

def g(u, v):
    return 20 * u + v
(n, q) = map(int, input().split())
(G, s0) = make_graph1(n, n - 1)
(t1, t2, dist, parent) = euler_tour()
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
p = [t1[i] << 20 ^ i for i in range(1, n + 1)]
p = [i & 1048575 for i in sorted(p)]
dp = [-1] * (20 * (n + 1))
for i in range(1, n + 1):
    dp[g(i, 0)] = parent[i]
for i in p:
    k = parent[i]
    for j in range(1, 20):
        if k == -1:
            break
        k = dp[g(k, j - 1)]
        dp[g(i, j)] = k
a = []
s1 = [0] * (q + 1)
x = [0] * (2 * q)
for i in range(q):
    t = list(map(int, input().split()))
    (x[2 * i], x[2 * i + 1]) = (t[0], i)
    for j in t[2:]:
        a.append(j)
    s1[i + 1] = len(a)
(Q, s2) = make_graph2(n, q)
l1 = pow(2, (2 * n + 1).bit_length())
l2 = 2 * l1
inf = 1 << 30
(tree, lazy) = ([-inf] * l2, [0] * l2)
for i in range(1, n + 1):
    tree[t1[i] + l1] = dist[i]
    tree[t2[i] + l1] = dist[i]
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
st = [1]
now = list(s0)
ans = [0] * q
visit = [0] * (n + 1)
while st:
    i = st[-1]
    if not visit[i]:
        (li, ri) = (t1[i], t2[i])
        for u in range(s2[i], s2[i + 1]):
            (j, z) = (Q[u], [l1 - 1 << 1])
            (ll, rr) = (-inf, inf)
            for v in range(s1[j], s1[j + 1]):
                k = a[v]
                (lk, rk) = (t1[k], t2[k])
                if not lk < li < ri < rk:
                    z.append(lk << 1)
                    z.append(rk << 1 ^ 1)
                else:
                    d = dist[i] - dist[k] - 1
                    k = i
                    for l in range(20):
                        if not d:
                            break
                        if d & pow2[l]:
                            d ^= pow2[l]
                            k = dp[g(k, l)]
                    (lk, rk) = (t1[k], t2[k])
                    (ll, rr) = (max(ll, lk), min(rr, rk))
            (l0, c, ans0) = (1, 0, -inf)
            for v in sorted(z):
                if not c:
                    r0 = (v >> 1) - 1
                    ans0 = max(ans0, get_max(max(ll, l0), min(rr, r0)))
                if v & 1:
                    c += 1
                else:
                    c -= 1
                if not c:
                    l0 = (v >> 1) + 1
            ans0 += dist[i]
            ans[j] = ans0
        visit[i] = 1
    if now[i] < s0[i + 1] and visit[G[now[i]]]:
        now[i] += 1
    if now[i] < s0[i + 1]:
        j = G[now[i]]
        (lj, rj) = (t1[j], t2[j])
        update(lj, rj, -2)
        now[i] += 1
        st.append(j)
    else:
        j = i
        (lj, rj) = (t1[j], t2[j])
        update(lj, rj, 2)
        st.pop()
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
import os
from io import BytesIO, IOBase
from _collections import deque
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
file = sys.stdin
if os.environ.get('USER') == 'loic':
    file = open('data.in')
line = lambda : file.readline().split()
ui = lambda : int(line()[0])
mi = lambda : map(int, line())
li = lambda : list(mi())
lsi = lambda : list(map(int, line()[0]))

def union(ranges):
    res = []
    if not ranges:
        return res
    (ent, out) = zip(*ranges)
    ent = sorted(list(ent))
    out = sorted(list(out))
    c = 0
    st = None
    i = 0
    j = 0
    sz = len(ranges)
    while i < sz:
        while j < sz and out[j] < ent[i]:
            c -= 1
            if c == 0:
                res.append((st, out[j]))
            j += 1
        if c == 0:
            st = ent[i]
        c += 1
        i += 1
    res.append((st, out[-1]))
    return res

class LazySegmentTree:

    def __init__(self, n):
        self.n = n
        self.h = (n - 1).bit_length()
        self.sz = 1 << self.h
        self.node = [self._neutral() for _ in range(2 * self.sz)]
        self.prop = [0] * 2 * self.sz
        self.upd = [0] * 2 * self.sz

    def build(self, arr):
        assert len(arr) == self.n
        for i in range(self.n):
            self.node[self.sz + i] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.node[i] = self._merge(self.node[i << 1], self.node[i << 1 | 1])

    def update(self, l, r, updated_val):
        tl = self.sz + l
        tr = self.sz + r
        for k in range(self.h, 0, -1):
            self._propagate(tl >> k)
            self._propagate(tr >> k)
        tl = self.sz + l
        tr = self.sz + r + 1
        left = 0
        right = 0
        while tl < tr:
            if tl & 1:
                self._apply(tl, updated_val)
                if not left:
                    left = tl
                tl += 1
            if tr & 1:
                tr -= 1
                self._apply(tr, updated_val)
                if not right:
                    right = tr
            tl >>= 1
            tr >>= 1
        left >>= 1
        while left:
            self.node[left] = self._merge(self.node[left << 1], self.node[left << 1 | 1])
            left >>= 1
        right >>= 1
        while right:
            self.node[right] = self._merge(self.node[right << 1], self.node[right << 1 | 1])
            right >>= 1

    def query(self, l, r):
        tl = self.sz + l
        tr = self.sz + r
        for k in range(self.h, 0, -1):
            self._propagate(tl >> k)
            self._propagate(tr >> k)
        tl = self.sz + l
        tr = self.sz + r + 1
        res_left = self._neutral()
        res_right = self._neutral()
        while tl < tr:
            if tl & 1:
                res_left = self._merge(res_left, self.node[tl])
                tl += 1
            if tr & 1:
                tr -= 1
                res_right = self._merge(self.node[tr], res_right)
            tl >>= 1
            tr >>= 1
        return self._merge(res_left, res_right)

    def _propagate(self, pos):
        if self.upd[pos]:
            self._apply(pos << 1, self.prop[pos])
            self._apply(pos << 1 | 1, self.prop[pos])
            self.upd[pos] = 0
            self.prop[pos] = self._neutral()

    def _apply(self, pos, propagated_val):
        self.upd[pos] = 1
        self.prop[pos] += propagated_val
        self.node[pos] += propagated_val

    def _merge(self, left, right):
        return max(left, right)

    def _neutral(self):
        return 0

    def __repr__(self):
        res = []
        for i in range(min(self.sz, 100)):
            res.append(self.query(i, i))
        return ' '.join((str(v) for v in res))

def solve():
    res = [0] * Q
    g = G
    start = 0
    seen = [-1] * len(g)
    q = deque([start])
    seen[start] = 0
    trace = [0]
    ent = [0] * N
    out = [0] * N
    h = [0] * N
    c = 1
    while q:
        n = q[-1]
        chs = g[n]
        nb = seen[n]
        if nb == len(chs):
            q.pop()
            trace.append(h[n])
            out[n] = c
            c += 1
        else:
            ch = chs[nb]
            if seen[ch] == -1:
                seen[ch] = 0
                q.append(ch)
                h[ch] = h[n] + 1
                trace.append(h[ch])
                ent[ch] = c
                c += 1
            seen[n] += 1
    sz = 2 * N
    st = LazySegmentTree(sz)
    st.build(trace)
    seen = [-1] * len(g)
    q = deque([start])
    seen[start] = 0
    nxt = [None] * N
    while q:
        n = q[-1]
        chs = g[n]
        nb = seen[n]
        if nb == len(chs):
            q.pop()
            for (idx, ks) in QS[n]:
                itv = [(-1, -1), (sz, sz)]
                for k in ks:
                    if ent[k] < ent[n] and out[k] > out[n]:
                        itv.append((0, ent[nxt[k]] - 1))
                        itv.append((out[nxt[k]] + 1, sz - 1))
                    else:
                        itv.append((ent[k], out[k]))
                itv = union(itv)
                mx = 0
                for i in range(1, len(itv)):
                    if itv[i][0] - 1 >= itv[i - 1][1] + 1:
                        mx = max(mx, st.query(itv[i - 1][1] + 1, itv[i][0] - 1))
                res[idx] = mx
            st.update(0, sz - 1, -1)
            st.update(ent[n], out[n], 2)
        else:
            ch = chs[nb]
            if seen[ch] == -1:
                seen[ch] = 0
                q.append(ch)
                nxt[n] = ch
                st.update(0, sz - 1, 1)
                st.update(ent[ch], out[ch], -2)
            seen[n] += 1
    return '\n'.join((str(v) for v in res))
for test in range(1, 1 + 1):
    (N, Q) = mi()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        (u, v) = mi()
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
    QS = [[] for _ in range(N)]
    for idx in range(Q):
        data = li()
        n = data[0] - 1
        QS[n].append((idx, [k - 1 for k in data[2:]]))
    print(solve())
file.close()