Minimum Maximum Distance (Codeforces 1881F)
Tags: DP, shortest paths

You have a tree with $$$n$$$ vertices, some of which are marked. A tree is a connected undirected graph without cycles.Let $$$f_i$$$ denote the maximum distance from vertex $$$i$$$ to any of the marked vertices.Your task is to find the minimum value of $$$f_i$$$ among all vertices.  For example, in the tree shown in the example, vertices $$$2$$$, $$$6$$$, and $$$7$$$ are marked. Then the array $$$f(i) = [2, 3, 2, 4, 4, 3, 3]$$$. The minimum $$$f_i$$$ is for vertices $$$1$$$ and $$$3$$$.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree and the number of marked vertices, respectively.The second line of each test case contains $$$k$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n, a_{i-1} < a_i$$$) — the indices of the marked vertices.The next $$$n - 1$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$ — the indices of vertices connected by the $$$i$$$-th edge.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the minimum value of $$$f_i$$$ among all vertices.


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

3
6 1
3
1 2
1 3
3 4
3 5
2 6
5 3
1 2 5
1 2
1 3
2 4
3 5
7 1
2
3 2
2 6
6 1
5 6
7 6
4 5

Sample Outputs:
2
2
0
1
4
5

0
2
0

Solution (Python):
from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

def ii():
    return int(input())

def si():
    return input()

def ls():
    return input().split()

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

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

def bfs(start, tree):
    q = deque([start])
    dist = [-1] * (len(tree) + 1)
    dist[start] = 0
    while q:
        parent = q.popleft()
        for child in tree[parent]:
            if dist[child] == -1:
                dist[child] = dist[parent] + 1
                q.append(child)
    return dist

def get_answer():
    test = ii()
    for _ in range(test):
        (n, k) = mi()
        marked = li()
        graph = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            (u, v) = map(int, input().split())
            graph[u].append(v)
            graph[v].append(u)
        if k == 1:
            print(0)
            continue
        dist = bfs(1, graph)
        first_farthest_marked = -1
        maxi = 0
        for m in marked:
            if dist[m] > maxi:
                maxi = dist[m]
                first_farthest_marked = m
        dist = bfs(first_farthest_marked, graph)
        maxi = max((dist[m] for m in marked))
        print((maxi + 1) // 2)
get_answer()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

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

def readInt():
    return int(input())

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

def readStr():
    return input().strip()

def solve():
    (n, k) = readInts()
    arr = readList()
    graph = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (u, v) = readInts()
        graph[u].append(v)
        graph[v].append(u)
    marked = [0] * (n + 1)
    for v in arr:
        marked[v] = 1
    n = len(graph) - 1
    s = [i for i in range(1, n + 1) if marked[i]][0]
    qu = deque([(s, 0)])
    vis = [0] * (n + 1)
    vis[s] = 1
    t = s
    while qu:
        (node, d) = qu.popleft()
        if marked[node]:
            t = node
        for nei in graph[node]:
            if not vis[nei]:
                vis[nei] = 1
                qu.append((nei, d + 1))
    vis = [0] * (n + 1)
    vis[t] = 1
    qu = deque([(t, 0)])
    prev = [0] * (n + 1)
    s = t
    while qu:
        (node, d) = qu.popleft()
        if marked[node]:
            s = node
        for nei in graph[node]:
            if not vis[nei]:
                vis[nei] = 1
                qu.append((nei, d + 1))
                prev[nei] = node
    if s == t:
        return 0
    cnt = 1
    while prev[s] != t:
        s = prev[s]
        cnt += 1
    return (cnt + 1) // 2
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def solve():
    (n, k) = list(map(int, input().split()))
    l = list(map(int, input().split()))
    adj = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (a, b) = list(map(int, input().split()))
        adj[a].append(b)
        adj[b].append(a)
    kNodes = [0 for i in range(n + 1)]
    for i in l:
        kNodes[i] = 1

    def farthestNode(node):
        q = deque()
        q.append((node, -1))
        lastNode = node
        dist = 0
        lastDist = 0
        while len(q) > 0:
            l = len(q)
            for k in range(l):
                (node, par) = q.popleft()
                if kNodes[node] == 1:
                    lastNode = node
                    lastDist = dist
                for nex in adj[node]:
                    if nex != par:
                        q.append((nex, node))
            dist += 1
        return (lastNode, lastDist)
    v1 = l[0]
    v2 = farthestNode(v1)[0]
    (v3, d) = farthestNode(v2)
    print(d // 2 + d % 2)
for _ in range(int(input())):
    solve()