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 endpoint of the longest diameter from given set
• Calculating distance using LCM from above node to all nodes present in set, answer is (maximum distance / 2).

To Calculate Endpoint

• Fix an arbitrary vertex let it be x.
• Find the furthest vertex from x, let it be req_node.
• req_node is Endpoint.

It is failing on 4/8 testcases.

Concept Used:

• Lowest Common Ancestor — Binary Lifting: Binary Lifting (CP Algorithm),
• Diameter of Tree & Application: Blog