Timofey and Black-White Tree (Codeforces 1790F)
Tags: Greedy, divide and conquer

Timofey came to a famous summer school and found a tree on $$$n$$$ vertices. A tree is a connected undirected graph without cycles.Every vertex of this tree, except $$$c_0$$$, is colored white. The vertex $$$c_0$$$ is colored black.Timofey wants to color all the vertices of this tree in black. To do this, he performs $$$n - 1$$$ operations. During the $$$i$$$-th operation, he selects the vertex $$$c_i$$$, which is currently white, and paints it black.Let's call the positivity of tree the minimum distance between all pairs of different black vertices in it. The distance between the vertices $$$v$$$ and $$$u$$$ is the number of edges on the path from $$$v$$$ to $$$u$$$.After each operation, Timofey wants to know the positivity of the current tree.

Input: The first line contains the integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains the integers $$$n, c_0$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le c_0 \le n$$$) — the number of vertices in the tree and index of the initial black vertex.The second line of each testcase contains $$$n - 1$$$ unique integers $$$c_1, c_2, \dots, c_{n-1}$$$ ($$$1 \le c_i \le n$$$, $$$c_i \ne c_0$$$), where $$$c_i$$$ is the vertex which is colored black during the $$$i$$$-th operation.Each of the next $$$n - 1$$$ row of each testcase contains the integers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — edges in the tree.It is guaranteed that the sum of $$$n$$$ for all testcases does not exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print $$$n - 1$$$ integer on a separate line.The integer with index $$$i$$$ must be equal to positivity of the tree obtained by the first $$$i$$$ operations.

Note: In the first testcase, after the second operation, the tree looks like this: The distance between vertices $$$1$$$ and $$$6$$$ is $$$3$$$, the distance between vertices $$$4$$$ and $$$6$$$ is $$$3$$$, the distance between vertices $$$1$$$ and $$$4$$$ is $$$2$$$. The positivity of this tree is equal to the minimum of these distances. It equals $$$2$$$.In the third testcase, after the fourth operation, the tree looks like this: The positivity of this tree is $$$2$$$.

Sample Inputs:
6
6 6
4 1 3 5 2
2 4
6 5
5 3
3 4
1 3
4 2
4 1 3
3 1
2 3
1 4
10 3
10 7 6 5 2 9 8 1 4
1 2
1 3
4 5
4 3
6 4
8 7
9 8
10 8
1 8
7 3
7 5 1 2 4 6
1 2
3 2
4 5
3 4
6 5
7 6
9 7
9 3 1 4 2 6 8 5
4 1
8 9
4 8
2 6
7 3
2 4
3 5
5 4
10 2
1 8 5 10 6 9 4 3 7
10 7
7 8
3 6
9 7
7 6
4 2
1 6
7 5
9 2

Sample Outputs:
3 2 1 1 1 
3 1 1 
3 2 2 2 2 2 1 1 1 
4 2 2 1 1 1 
5 1 1 1 1 1 1 1 
4 3 2 2 1 1 1 1 1

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

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')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
    (n, root) = map(int, input().split())
    order = list(map(int, input().split()))
    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (x, y) = map(int, input().split())
        tree[x].append(y)
        tree[y].append(x)
    parents = [-1] * (n + 1)
    queue = deque([(root, -1)])
    distances = [0] * (n + 1)
    while queue:
        (node, parent) = queue.popleft()
        dist = distances[node] + 1
        for child in tree[node]:
            if child == parent:
                continue
            parents[child] = node
            distances[child] = dist
            queue.append((child, node))
    answer = [1] * (n - 1)
    for (i, x) in enumerate(order):
        dist = distances[x]
        if i and dist > answer[i - 1]:
            dist = answer[i - 1]
        d = 0
        distances[x] = 0
        p = parents[x]
        while p != -1:
            x = p
            d += 1
            if d >= dist:
                break
            dist = min(dist, d + distances[x])
            if distances[x] <= d:
                break
            distances[x] = d
            p = parents[x]
        if dist == 1:
            break
        answer[i] = dist
    return answer

def main():
    n_cases = int(input())
    for _ in range(n_cases):
        sys.stdout.write(' '.join(map(repr, solve())))
        sys.stdout.write('\n')
main()

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 4096

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, **kwargs):
        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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from collections import Counter, defaultdict, deque
MOD = int(1000000000.0 + 7)
INF = int(1e+20)

def solve():
    (n, root) = MI()
    a = [root] + LII()
    g = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (x, y) = MI()
        g[x].append(y)
        g[y].append(x)
    pv = [0] * (n + 1)
    pv[root] = -1
    q = [root]
    while q:
        v = q.pop()
        for u in g[v]:
            if u == pv[v]:
                continue
            pv[u] = v
            q.append(u)
    ans = n + 1
    best = [ans] * (n + 1)
    for i in range(n):
        v = a[i]
        val = 0
        while v >= 0 and val < ans:
            ans = min(ans, val + best[v])
            best[v] = min(best[v], val)
            v = pv[v]
            val += 1
        if i > 0:
            print(ans, end=' ')
N = II()
for _ in range(N):
    solve()
    print()

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 4096

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, **kwargs):
        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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from collections import Counter, defaultdict, deque
MOD = int(1000000000.0 + 7)
INF = int(1e+20)

def solve():
    (n, root) = map(int, input().split())
    order = list(map(int, input().split()))
    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (x, y) = map(int, input().split())
        tree[x].append(y)
        tree[y].append(x)
    parents = [-1] * (n + 1)
    queue = deque([(root, -1)])
    distances = [0] * (n + 1)
    while queue:
        (node, parent) = queue.popleft()
        dist = distances[node] + 1
        for child in tree[node]:
            if child == parent:
                continue
            parents[child] = node
            distances[child] = dist
            queue.append((child, node))
    answer = [1] * (n - 1)
    for (i, x) in enumerate(order):
        dist = distances[x]
        if i and dist > answer[i - 1]:
            dist = answer[i - 1]
        d = 0
        distances[x] = 0
        p = parents[x]
        while p != -1:
            x = p
            d += 1
            if d >= dist:
                break
            dist = min(dist, d + distances[x])
            if distances[x] <= d:
                break
            distances[x] = d
            p = parents[x]
        if dist == 1:
            break
        answer[i] = dist
    print(*answer)
    return
N = II()
for _ in range(N):
    solve()