Problem statement

https://binarysearch.com/problems/Tag-Game-in-a-Tree/

Solution

Let us for each node calculate distance from u and from v. Let us consider only nodes, for which the second player can reach it before us. Among all this nodes we calculate dist1[i] * 2 - 1 is number of moves we can make: first player need dist1[i] moves and because it starts first, we subtract 1.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, edges, u, v):
        G = defaultdict(list)
        for x, y in edges:
            G[x] += [y]
            G[y] += [x]

        n = len(edges) + 1
        dist1 = [0] * n
        dist2 = [0] * n

        def dfs(node, par, d, dist):
            dist[node] = d
            for child in G[node]:
                if child == par: continue
                dfs(child, node, d + 1, dist)

        dfs(u, -1, 0, dist1)
        dfs(v, -1, 0, dist2)
        ans = 1

        for i in range(n):
            if dist2[i] + 1 < dist1[i]:
                ans = max(ans, dist1[i] * 2 - 1)

        return ans