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
