Cycle Length Queries In A Tree - Leetcode Solution

Problem Statement:

Given a tree consisting of n nodes numbered from 0 to n-1. You are given q queries, where each query contains two integers u and v. You have to find the length of the cycle between the nodes u and v.

A cycle is defined as a path of nonzero length in the tree that starts and ends at the same node.

Solution:

To solve this problem, we can use LCA (Lowest Common Ancestor) and binary lifting approach.

1. Create an adjacency list to store the graph.

2. Create two arrays: depth and parent. The depth array stores the depth of each node and parent array stores the parent node of each node.

3. Compute the depth and parent arrays using dfs (depth-first search) traversal.

4. Calculate the LCA of u and v using binary lifting. In binary lifting, we precompute the 2^i th parent of each node and use it to jump up the tree in logarithmic time.

5. Compute the distance between u and the LCA and v and the LCA.

6. The distance between u and v is the sum of the distance between u and the LCA, v and LCA, and the distance between LCA and LCA itself (since LCA is counted twice).

7. Return the distance between u and v.

Code:

Here is the implementation of the above approach in python:

from collections import defaultdict

class Solution: def init(self): self.adj = defaultdict(list) self.depth = [0] * n self.parent = [[0] * 20 for _ in range(n)]

def addEdge(self, u, v):
    self.adj[u].append(v)
    self.adj[v].append(u)

def dfs(self, node, par, d):
    self.depth[node] = d
    self.parent[node][0] = par
    for nbr in self.adj[node]:
        if nbr != par:
            self.dfs(nbr, node, d + 1)

def precompute(self):
    self.dfs(0, -1, 0)
    for i in range(1, 20):
        for j in range(n):
            if self.parent[j][i - 1] != -1:
                self.parent[j][i] = self.parent[self.parent[j][i - 1]][i - 1]

def binaryLift(self, u, v):
    if self.depth[u] < self.depth[v]:
        u, v = v, u
    diff = self.depth[u] - self.depth[v]
    for i in range(20):
        if (diff >> i) & 1:
            u = self.parent[u][i]
    if u == v:
        return u
    for i in range(19, -1, -1):
        if self.parent[u][i] != self.parent[v][i]:
            u = self.parent[u][i]
            v = self.parent[v][i]
    return self.parent[u][0]

def distance(self, u, v):
    lca = self.binaryLift(u, v)
    dist = self.depth[u] + self.depth[v] - 2 * self.depth[lca] + 1
    return dist

def solve(self, n: int, q: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
    self.adj = defaultdict(list)
    for e in edges:
        self.addEdge(e[0], e[1])
    self.precompute()

    ans = []
    for q in queries:
        res = self.distance(q[0], q[1])
        ans.append(res)
    return ans

The time complexity of this approach is O(n log n) for precomputing the parent array and O(q log n) for answering each query. The space complexity is O(n log n) for storing the parent array.

1