Graph Theory37 sections · 1633 units
Open in Course

Quiz: Sum of Distances

Knowledge check

Check Your Understanding

Tree Distances II: For each node, compute sum of distances to all other nodes. Naive approach is O(n2)O(n^2). What technique makes it O(n)O(n)?

  1. A.Precompute all pairwise distances
  2. B.Rerooting DP
  3. C.Binary search on distances
  4. D.BFS from the center only
Start the roadmap to answer the quizzes and solve the challenges