Copil Copac Draws Trees (Codeforces 1831C)
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):
from collections import defaultdict, deque
import sys
input = sys.stdin.readline

def bfs(g):
    visited = dict()
    ans = 1
    queue = deque()
    queue.append([0, 1, -1])
    visited[0] = 0
    while queue:
        (u, c, i) = queue.pop()
        ans = max(ans, c)
        for v in g[u]:
            if visited.get(v, 1):
                visited[v] = 0
                queue.append([v, c + (1 if g[u][v] < i else 0), g[u][v]])
    return ans

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        g = defaultdict(dict)
        for i in range(n - 1):
            (u, v) = map(int, input().split())
            g[u - 1][v - 1] = i
            g[v - 1][u - 1] = i
        print(bfs(g))
main()

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

def bfs(g):
    visited = [1] * len(g)
    ans = 1
    queue = deque()
    queue.append([0, 1, -1])
    visited[0] = 0
    while queue:
        (u, c, i) = queue.pop()
        ans = max(ans, c)
        for v in g[u]:
            if visited[v]:
                visited[v] = 0
                queue.append([v, c + (1 if g[u][v] < i else 0), g[u][v]])
    return ans

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        g = defaultdict(dict)
        for i in range(n - 1):
            (u, v) = map(int, input().split())
            g[u - 1][v - 1] = i
            g[v - 1][u - 1] = i
        print(bfs(g))
main()

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

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 = readInt()
    graph = [[] for _ in range(n)]
    for i in range(n - 1):
        (u, v) = readInts()
        graph[u - 1].append((v - 1, i))
        graph[v - 1].append((u - 1, i))
    qu = deque([(0, -1)])
    ans = [-1] * n
    ans[0] = 1
    while qu:
        (node, idx) = qu.popleft()
        for (nei, j) in graph[node]:
            if ans[nei] == -1:
                ans[nei] = ans[node] if j > idx else ans[node] + 1
                qu.append((nei, j))
    return max(ans)
for _ in range(int(input())):
    print(solve())