Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

HELP — Stuck on this Problem from yesterday!!

Revision en2, by stash, 2023-05-22 12:48:35

Problem — Minimum Ugliness Appeared in the Wednesday contest on CodeChef.

My Solution — https://www.codechef.com/viewsolution/96660756

Approach (Using Binary Uplifting) →

  • (Precomputing) Binary Uplifting using DFS.
  • For Each query, identifying one node of longest diameter from given set
  • Calculating distance from above node to all nodes present in set, answer is (maximum distance / 2).

It is failing on 4/8 testcases.

Concept Used: Binary lifting: Binary Lifting (CP Algorithm), Diameter of Tree & Application: Blog

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English stash 2023-05-22 13:00:22 233 Tiny change: 'g.html),\n- Diameter o' -> 'g.html),\nDiameter o' (published)
en2 English stash 2023-05-22 12:48:35 37 Tiny change: 'ution/96669203\n\nApproa' -> 'ution/96660756\n\nApproa'
en1 English stash 2023-05-22 12:43:17 755 Initial revision (saved to drafts)