Sasha and the Happy Tree Cutting (Codeforces 1929E)
Tags: Greedy, trees

Sasha was given a tree$$$^{\dagger}$$$ with $$$n$$$ vertices as a prize for winning yet another competition. However, upon returning home after celebrating his victory, he noticed that some parts of the tree were missing. Sasha remembers that he colored some of the edges of this tree. He is certain that for any of the $$$k$$$ pairs of vertices $$$(a_1, b_1), \ldots, (a_k, b_k)$$$, he colored at least one edge on the simple path$$$^{\ddagger}$$$ between vertices $$$a_i$$$ and $$$b_i$$$.Sasha does not remember how many edges he exactly colored, so he asks you to tell him the minimum number of edges he could have colored to satisfy the above condition.$$$^{\dagger}$$$A tree is an undirected connected graph without cycles.$$$^{\ddagger}$$$A simple path is a path that passes through each vertex at most once.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.The next $$$(n - 1)$$$ lines describe the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — the numbers of the vertices connected by the $$$i$$$-th edge.The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 20$$$) — the number of pairs of vertices between which Sasha colored at least one edge on a simple path.The next $$$k$$$ lines describe pairs. The $$$j$$$-th line contains two integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \leq a_j, b_j \leq n, a_j \neq b_j$$$) — the vertices in the $$$j$$$-th pair.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$. It is guaranteed that the sum of $$$2^k$$$ over all test cases does not exceed $$$2^{20}$$$.

Output: For each test case, output a single integer — the minimum number of edges Sasha could have colored.

Note: In the first test case, Sasha could have colored only one edge $$$(1, 2)$$$. Then, there would be at least one colored edge on the simple path between vertices $$$1$$$ and $$$3$$$, and vertices $$$4$$$ and $$$1$$$.  In the second test case, Sasha could have colored the edges $$$(1, 6)$$$ and $$$(1, 3)$$$.  

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

Sample Outputs:
1
2
4

Solution (Python):
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def compress(n, k, adj, pairs):
    """"""
    in_pairs = [0] * n
    for (a, b) in pairs:
        in_pairs[a] = in_pairs[b] = 1
    root = 0
    preserve = [0] * n
    preserve[root] = 1

    @bootstrap
    def dfs(u, p):
        cnt = 0
        for v in adj[u]:
            if v != p:
                cnt += (yield dfs(v, u))
        if cnt > 1 or in_pairs[u] == 1:
            preserve[u] = 1
        if cnt >= 1 or in_pairs[u] == 1:
            yield 1
        else:
            yield 0
    dfs(root, -1)
    new_par = [-1] * n
    st = [(root, root, -1)]
    while st:
        (u, unremoved_ancestor, prev) = st.pop()
        if preserve[u] == 1:
            unremoved_ancestor = u
        for v in adj[u]:
            if v != prev:
                if preserve[v] == 1:
                    new_par[v] = unremoved_ancestor
                st.append((v, unremoved_ancestor, u))
    new_nodes = []
    for u in range(n):
        if preserve[u] == 1:
            new_nodes.append(u)
    new_n = len(new_nodes)
    assert new_n <= 80
    rev_map = dict()
    for (i, u) in enumerate(new_nodes):
        rev_map[u] = i
    new_adj = [[] for _ in range(new_n)]
    for u in new_nodes:
        if u != root:
            v = new_par[u]
            assert v != -1
            u2 = rev_map[u]
            v2 = rev_map[v]
            new_adj[u2].append(v2)
            new_adj[v2].append(u2)
    new_pairs = []
    for (a, b) in pairs:
        a2 = rev_map[a]
        b2 = rev_map[b]
        new_pairs.append((a2, b2))
    return (new_n, k, new_adj, new_pairs)

def solve(n, k, adj, pairs):
    assert n <= 80
    par = [-1] * n
    root = 0
    par[root] = -2
    depth = [0] * n
    st = [root]
    while st:
        u = st.pop()
        for v in adj[u]:
            if par[v] == -1:
                par[v] = u
                depth[v] = depth[u] + 1
                st.append(v)
    edges = [0] * (n * n)
    for (i, (a, b)) in enumerate(pairs):
        (u, v) = (a, b)
        while u != v:
            if depth[u] < depth[v]:
                (u, v) = (v, u)
            u2 = par[u]
            U = min(u, u2)
            V = max(u, u2)
            u = u2
            KEY = U * n + V
            edges[KEY] |= 1 << i
    dp = [k + 1] * (1 << k)
    dp[0] = 0
    for v in edges:
        if v == 0:
            continue
        dp2 = dp.copy()
        for mask in range(1 << k):
            mask3 = mask | v
            dp2[mask3] = min(dp2[mask3], dp[mask] + 1)
        dp = dp2
    return dp[(1 << k) - 1]

def test():
    from random import randint

    class UnionFind:

        def __init__(self, n):
            self.parent = list(range(n))

        def find(self, a):
            acopy = a
            while a != self.parent[a]:
                a = self.parent[a]
            while acopy != a:
                (self.parent[acopy], acopy) = (a, self.parent[acopy])
            return a

        def union(self, a, b):
            self.parent[self.find(b)] = self.find(a)
    n = 10
    k = 4
    for _ in range(10000):
        adj = [[] for __ in range(n)]
        uf = UnionFind(n)
        for __ in range(n - 1):
            while True:
                (u, v) = [randint(0, n - 1) for ___ in range(2)]
                if uf.find(u) != uf.find(v):
                    uf.union(u, v)
                    adj[u].append(v)
                    adj[v].append(u)
                    break
        pairs = set()
        while len(pairs) < k:
            (u, v) = [randint(0, n - 1) for ___ in range(2)]
            if u != v:
                pairs.add((u, v))
        (n2, k, adj2, pairs2) = compress(n, k, adj, pairs)
        ans1 = solve(n, k, adj, pairs)
        ans2 = solve(n2, k, adj2, pairs2)
        if ans1 != ans2:
            print(f'adj={adj} pairs={pairs}\nadj2={adj2} pairs2={pairs2}\nans1={ans1} ans2={ans2}')
            raise Exception
    n = 100000
    k = 20
    adj = [[] for __ in range(n)]
    uf = UnionFind(n)
    for __ in range(n - 1):
        while True:
            (u, v) = [randint(0, n - 1) for ___ in range(2)]
            if uf.find(u) != uf.find(v):
                uf.union(u, v)
                adj[u].append(v)
                adj[v].append(u)
                break
    pairs = set()
    while len(pairs) < k:
        (u, v) = [randint(0, n - 1) for ___ in range(2)]
        if u != v:
            pairs.add((u, v))
    print('start')
    (n2, k, adj2, pairs2) = compress(n, k, adj, pairs)
    print(f'n2={n2}')
    ans2 = solve(n2, k, adj2, pairs2)
    print(f'ans={ans2}')
    return

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        adj = [[] for _ in range(n)]
        for __ in range(n - 1):
            (u, v) = readIntArr()
            u -= 1
            v -= 1
            adj[u].append(v)
            adj[v].append(u)
        k = int(input())
        pairs = []
        for __ in range(k):
            (a, b) = readIntArr()
            a -= 1
            b -= 1
            pairs.append((a, b))
        (new_n, k, new_adj, new_pairs) = compress(n, k, adj, pairs)
        ans = solve(new_n, k, new_adj, new_pairs)
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def compress(n, k, adj, pairs):
    """"""
    in_pairs = [0] * n
    for (a, b) in pairs:
        in_pairs[a] = in_pairs[b] = 1
    root = 0
    preserve = [0] * n
    preserve[root] = 1

    @bootstrap
    def dfs(u, p):
        cnt = 0
        for v in adj[u]:
            if v != p:
                cnt += (yield dfs(v, u))
        if cnt > 1 or in_pairs[u] == 1:
            preserve[u] = 1
        if cnt >= 1 or in_pairs[u] == 1:
            yield 1
        else:
            yield 0
    dfs(root, -1)
    new_par = [-1] * n
    st = [(root, root, -1)]
    while st:
        (u, unremoved_ancestor, prev) = st.pop()
        if preserve[u] == 1:
            unremoved_ancestor = u
        for v in adj[u]:
            if v != prev:
                if preserve[v] == 1:
                    new_par[v] = unremoved_ancestor
                st.append((v, unremoved_ancestor, u))
    new_nodes = []
    for u in range(n):
        if preserve[u] == 1:
            new_nodes.append(u)
    new_n = len(new_nodes)
    assert new_n <= 80
    rev_map = dict()
    for (i, u) in enumerate(new_nodes):
        rev_map[u] = i
    new_adj = [[] for _ in range(new_n)]
    for u in new_nodes:
        if u != root:
            v = new_par[u]
            assert v != -1
            u2 = rev_map[u]
            v2 = rev_map[v]
            new_adj[u2].append(v2)
            new_adj[v2].append(u2)
    new_pairs = []
    for (a, b) in pairs:
        a2 = rev_map[a]
        b2 = rev_map[b]
        new_pairs.append((a2, b2))
    return (new_n, k, new_adj, new_pairs)

def solve(n, k, adj, pairs):
    assert n <= 80
    par = [-1] * n
    root = 0
    par[root] = -2
    depth = [0] * n
    st = [root]
    while st:
        u = st.pop()
        for v in adj[u]:
            if par[v] == -1:
                par[v] = u
                depth[v] = depth[u] + 1
                st.append(v)
    edges = [0] * (n * n)
    for (i, (a, b)) in enumerate(pairs):
        (u, v) = (a, b)
        while u != v:
            if depth[u] < depth[v]:
                (u, v) = (v, u)
            u2 = par[u]
            U = min(u, u2)
            V = max(u, u2)
            u = u2
            KEY = U * n + V
            edges[KEY] |= 1 << i
    edges2 = []
    for mask in edges:
        if mask != 0:
            edges2.append(mask)
    best = [-1] * (1 << k)
    best[0] = 0
    from collections import deque
    q = deque([0])
    while q:
        mask = q.popleft()
        for mask2 in edges2:
            mask3 = mask | mask2
            if best[mask3] == -1:
                best[mask3] = best[mask] + 1
                q.append(mask3)
    return best[(1 << k) - 1]

def test():
    from random import randint

    class UnionFind:

        def __init__(self, n):
            self.parent = list(range(n))

        def find(self, a):
            acopy = a
            while a != self.parent[a]:
                a = self.parent[a]
            while acopy != a:
                (self.parent[acopy], acopy) = (a, self.parent[acopy])
            return a

        def union(self, a, b):
            self.parent[self.find(b)] = self.find(a)
    n = 10
    k = 4
    for _ in range(10000):
        adj = [[] for __ in range(n)]
        uf = UnionFind(n)
        for __ in range(n - 1):
            while True:
                (u, v) = [randint(0, n - 1) for ___ in range(2)]
                if uf.find(u) != uf.find(v):
                    uf.union(u, v)
                    adj[u].append(v)
                    adj[v].append(u)
                    break
        pairs = set()
        while len(pairs) < k:
            (u, v) = [randint(0, n - 1) for ___ in range(2)]
            if u != v:
                pairs.add((u, v))
        (n2, k, adj2, pairs2) = compress(n, k, adj, pairs)
        ans1 = solve(n, k, adj, pairs)
        ans2 = solve(n2, k, adj2, pairs2)
        if ans1 != ans2:
            print(f'adj={adj} pairs={pairs}\nadj2={adj2} pairs2={pairs2}\nans1={ans1} ans2={ans2}')
            raise Exception
    n = 100000
    k = 20
    adj = [[] for __ in range(n)]
    uf = UnionFind(n)
    for __ in range(n - 1):
        while True:
            (u, v) = [randint(0, n - 1) for ___ in range(2)]
            if uf.find(u) != uf.find(v):
                uf.union(u, v)
                adj[u].append(v)
                adj[v].append(u)
                break
    pairs = set()
    while len(pairs) < k:
        (u, v) = [randint(0, n - 1) for ___ in range(2)]
        if u != v:
            pairs.add((u, v))
    print('start')
    (n2, k, adj2, pairs2) = compress(n, k, adj, pairs)
    print(f'n2={n2}')
    ans2 = solve(n2, k, adj2, pairs2)
    print(f'ans={ans2}')
    return

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        adj = [[] for _ in range(n)]
        for __ in range(n - 1):
            (u, v) = readIntArr()
            u -= 1
            v -= 1
            adj[u].append(v)
            adj[v].append(u)
        k = int(input())
        pairs = []
        for __ in range(k):
            (a, b) = readIntArr()
            a -= 1
            b -= 1
            pairs.append((a, b))
        (new_n, k, new_adj, new_pairs) = compress(n, k, adj, pairs)
        ans = solve(new_n, k, new_adj, new_pairs)
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
p = 998244353

def process(n, G, A):
    g = [[] for i in range(n + 1)]
    for (u, v) in G:
        g[u].append(v)
        g[v].append(u)
    start = [[1]]
    parent = [None for i in range(n + 1)]
    parent[1] = -1
    while True:
        next_s = []
        for x in start[-1]:
            for y in g[x]:
                if parent[y] is None:
                    parent[y] = x
                    next_s.append(y)
        if len(next_s) == 0:
            break
        start.append(next_s)
    my_info = [0 for i in range(n + 1)]
    k = len(A)
    for i in range(k):
        R = 2 ** i
        (a, b) = A[i]
        path1 = [a]
        path2 = [b]
        while path1[-1] != 1:
            x = path1[-1]
            path1.append(parent[x])
        while path2[-1] != 1:
            x = path2[-1]
            path2.append(parent[x])
        while len(path1) > 0 and len(path2) > 0 and (path1[-1] == path2[-1]):
            x = path1.pop()
            path2.pop()
        for x in path1 + path2:
            my_info[x] = my_info[x] | R
    S = set([my_info[x] for x in range(n + 1)])
    d = set([])
    start = [0]
    I = 0
    while len(start) > 0:
        next_s = []
        for x in start:
            for y in S:
                if y | x == 2 ** k - 1:
                    print(I + 1)
                    return
                if y | x not in d:
                    d.add(y | x)
                    next_s.append(y | x)
        start = next_s
        I += 1
t = int(input())
for i in range(t):
    n = int(input())
    G = []
    for j in range(n - 1):
        (u, v) = [int(x) for x in input().split()]
        G.append([u, v])
    k = int(input())
    A = []
    for j in range(k):
        (a, b) = [int(x) for x in input().split()]
        A.append([a, b])
    process(n, G, A)