Festival Tree Diameter
Preview mode. Log in to edit, run, submit, and save progress.
Festival Tree Diameter
A festival installation starts as a small tree: checkpoint 1 is connected to leaves 2, 3, and 4. During the event, each operation chooses an existing leaf v and attaches two new leaves to v. After every operation, the operations team needs the current tree diameter: the maximum number of edges on a path between any two checkpoints. Input Format: The first line contains t. Each case starts with q, the number of operations. Each of the next q lines contains one valid leaf v chosen for expansion at that moment. Output Format: For every operation, print the diameter of the tree after the two new leaves are attached.
Examples
1 5 2 3 4 8 5
3
Explanation: The initial diameter is 2. Each expansion may or may not extend the farthest pair; the output shows the diameter after each operation.
Approach hint
Only two new leaves are added each time.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.