Copil Copac Draws Trees (Codeforces 1830A)
Tags: DP, trees

Copil Copac is given a list of $$$n-1$$$ edges describing a tree of $$$n$$$ vertices. He decides to draw it using the following algorithm:  Step $$$0$$$: Draws the first vertex (vertex $$$1$$$). Go to step $$$1$$$.  Step $$$1$$$: For every edge in the input, in order: if the edge connects an already drawn vertex $$$u$$$ to an undrawn vertex $$$v$$$, he will draw the undrawn vertex $$$v$$$ and the edge. After checking every edge, go to step $$$2$$$.  Step $$$2$$$: If all the vertices are drawn, terminate the algorithm. Else, go to step $$$1$$$. The number of readings is defined as the number of times Copil Copac performs step $$$1$$$.Find the number of readings needed by Copil Copac to draw the tree.

Input: Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the tree.The following $$$n - 1$$$ lines of each test case contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — indicating that $$$(u_i,v_i)$$$ is the $$$i$$$-th edge in the list. It is guaranteed that the given edges form a tree.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 the number of readings Copil Copac needs to draw the tree.

Note: In the first test case:After the first reading, the tree will look like this:  After the second reading:  Therefore, Copil Copac needs $$$2$$$ readings to draw the tree.

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

Sample Outputs:
2
3

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    d = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (a, b) = map(int, input().split())
        d[a].append((b, i))
        d[b].append((a, i))
    x = [(0, 0) for i in range(n + 1)]
    q = [(1, -1)]
    while q:
        (a, b) = q.pop()
        for (i, j) in d[a]:
            if i != b:
                if j < x[a][0]:
                    x[i] = (j, x[a][1] + 1)
                else:
                    x[i] = (j, x[a][1])
                q.append((i, a))
    print(max((i[1] for i in x)) + 1)

Solution (Python):
from collections import defaultdict, deque
for _ in range(int(input())):
    n = int(input()) - 1
    grid = defaultdict(dict)
    for i in range(n):
        (x, y) = map(int, input().split())
        grid[x][y] = i + 1
        grid[y][x] = i + 1
    dp = [n + 1 for _ in range(n + 2)]
    (dp[0], dp[1]) = (0, 1)
    edge = [-1 for _ in range(n + 2)]
    edge[1] = 0
    temp = deque([1])
    seen = set([1])
    while temp:
        cn = temp.popleft()
        for x in grid[cn].keys():
            if x in seen:
                continue
            if grid[cn][x] > edge[cn]:
                dp[x] = dp[cn]
            else:
                dp[x] = dp[cn] + 1
            edge[x] = grid[cn][x]
            seen.add(x)
            temp.append(x)
    print(max(dp))

Solution (Python):
from collections import deque
t = int(input())
for _ in range(t):
    n = int(input())
    visited = [False] * n
    ans = [0] * n
    val = [0] * n
    adj = [[] for _ in range(n)]
    M = 0
    val[0] = n
    for i in range(n - 1):
        (u, v) = map(int, input().split())
        adj[u - 1].append((v - 1, i))
        adj[v - 1].append((u - 1, i))
    Q = deque()
    Q.append(0)
    visited[0] = True
    while Q:
        p = Q.popleft()
        for (c, v) in adj[p]:
            if not visited[c]:
                ans[c] = ans[p]
                if v < val[p]:
                    ans[c] += 1
                val[c] = v
                visited[c] = True
                Q.append(c)
        M = max(M, ans[p])
    print(M)