Blocking Chips (Codeforces 1795F)
Tags: Greedy, trees

You are given a tree, consisting of $$$n$$$ vertices. There are $$$k$$$ chips, placed in vertices $$$a_1, a_2, \dots, a_k$$$. All $$$a_i$$$ are distinct. Vertices $$$a_1, a_2, \dots, a_k$$$ are colored black initially. The remaining vertices are white.You are going to play a game where you perform some moves (possibly, zero). On the $$$i$$$-th move ($$$1$$$-indexed) you are going to move the $$$((i - 1) \bmod k + 1)$$$-st chip from its current vertex to an adjacent white vertex and color that vertex black. So, if $$$k=3$$$, you move chip $$$1$$$ on move $$$1$$$, chip $$$2$$$ on move $$$2$$$, chip $$$3$$$ on move $$$3$$$, chip $$$1$$$ on move $$$4$$$, chip $$$2$$$ on move $$$5$$$ and so on. If there is no adjacent white vertex, then the game ends.What's the maximum number of moves you can perform?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the tree.Each of the next $$$n - 1$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the descriptions of the edges. The given edges form a tree.The next line contains a single integer $$$k$$$ ($$$1 \le k \le n$$$) — the number of chips.The next line contains $$$k$$$ integers $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_i \le n$$$) — the vertices with the chips. All $$$a_i$$$ are distinct.The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print a single integer — the maximum number of moves you can perform.


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

Sample Outputs:
2
0
1
2
0

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

def make_graph(n, m):
    (x, s) = ([], [0] * (n + 3))
    for _ in range(m):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x.append(u)
        x.append(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 bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [0] * (n + 1)
    for k in range(n):
        i = q[k]
        for u in range(s0[i], s0[i + 1]):
            j = G[u]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (q, parent)

def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if ok(m):
            c1 = m
        else:
            c2 = m
    m += 1
    while not ok(m):
        m -= 1
    return m

def ok(m):
    if m <= 0:
        return True
    c = [-1] * (n + 1)
    for i in range(m + k):
        c[a[i % k]] += 1
    dp1 = [0] * (n + 1)
    dp2 = [0] * (n + 1)
    cnt = 0
    for u in p:
        v = parent[u]
        if c[u] == -1:
            dp1[v] = max(dp1[v], dp1[u] + 1)
        elif dp1[u] + dp2[u] >= c[u]:
            cnt += 1
        else:
            if not v or dp2[v]:
                return False
            c[v] = c[u]
            dp2[v] = dp2[u] + 1
    return True if cnt == k else False
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    (G, s0) = make_graph(n, n - 1)
    k = int(input())
    a = list(map(int, input().split()))
    b = [0] * (n + 1)
    for i in a:
        b[i] = 1
    (p, parent) = bfs(1)
    p.reverse()
    ans0 = binary_search(0, n - k + 1)
    ans.append(ans0)
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_graph(n, m):
    (x, s) = ([], [0] * (n + 3))
    for _ in range(m):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x.append(u)
        x.append(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 bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [0] * (n + 1)
    for k in range(n):
        i = q[k]
        for u in range(s0[i], s0[i + 1]):
            j = G[u]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (q, parent)

def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if ok(m):
            c1 = m
        else:
            c2 = m
    m += 1
    while not ok(m):
        m -= 1
    return m

def ok(m):
    if m <= 0:
        return True
    c = [-1] * (n + 1)
    for i in range(m + k):
        c[a[i % k]] += 1
    dp1 = [0] * (n + 1)
    dp2 = [0] * (n + 1)
    cnt = 0
    for u in p:
        v = parent[u]
        if c[u] == -1:
            dp1[v] = max(dp1[v], dp1[u] + 1)
        elif dp1[u] + dp2[u] >= c[u]:
            cnt += 1
        else:
            if not v or dp2[v]:
                return False
            c[v] = c[u]
            dp2[v] = dp2[u] + 1
    return True if cnt == k else False
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    (G, s0) = make_graph(n, n - 1)
    k = int(input())
    a = list(map(int, input().split()))
    b = [0] * (n + 1)
    for i in a:
        b[i] = 1
    (p, parent) = bfs(1)
    p.reverse()
    ans0 = binary_search(0, n - k + 1)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
import random
from collections import deque
input = sys.stdin.buffer.readline
for _ in range(int(input())):
    n = int(input())
    g = [[] for _ in range(n + 1)]
    p = [0] * (n + 1)
    for _ in range(1, n):
        (u, v) = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
    q = deque()
    q.append(1)
    o = []
    while len(q):
        u = q.popleft()
        o.append(u)
        for v in g[u]:
            if p[u] != v:
                p[v] = u
                q.append(v)
    k = int(input())
    a = list(map(int, input().split()))
    o = o[::-1]
    (l, r) = (0, n - k)
    while l < r:
        m = (l + r + 1) // 2
        step = [-1] * (n + 1)
        for i in range(k):
            step[a[i]] = m // k + (i < m % k)
        ok = True
        for uu in o:
            if step[uu] == -1:
                continue
            q = deque()
            q.append(uu)
            down = False
            while len(q) > 0:
                u = q.popleft()
                if step[u] == 0:
                    down = True
                    break
                for v in g[u]:
                    if p[v] == u and step[v] == -1:
                        step[v] = step[u] - 1
                        q.append(v)
            if not down:
                if p[uu] == 0 or step[p[uu]] != -1:
                    ok = False
                    break
                step[p[uu]] = step[uu] - 1
        if ok:
            l = m
        else:
            r = m - 1
    print(l)