Giant Christmas Tree — Solution¶
Setter method: centroid decomposition for diameter maintenance under deletion. Codex (GPT-6): the reverse-time method, plus local Euler intervals, path operations, and iterative construction for the online method.
Reverse the deletions¶
A lit edge changes only when it is first extinguished. Root the tree at vertex 1 and preprocess parents, depths, and binary-lifting LCA. Represent each parent edge by its deeper endpoint. A separate skipping disjoint set bypasses consecutive already-dark parent edges; initialize it to skip edges that start dark.
For query \(u,v\) , find \(w=\operatorname{LCA}(u,v)\) . From each endpoint, call Find and, while its depth exceeds that of \(w\) , record its parent edge as first deleted by this query, then link it to Find(parent) . Each edge is recorded at most once. Test depth after jumping: the returned vertex may already be above \(w\) .
Build the lit forest after all operations. Each component stores its size, diameter length, and two diameter endpoints. Process queries backward: record the current global diameter before restoring edges first deleted by this query.
Merge component diameters¶
For endpoint pairs \((a,b)\) and \((c,d)\) , compare the two old diameters and four cross distances \(d(a,c),d(a,d),d(b,c),d(b,d)\) . Depths and LCA give each distance in \(O(\log N)\) . Once the components are joined, their unique path in the full tree lies entirely in the new component.
The needed lemma is that, for any diameter endpoints \(a,b\) , a farthest vertex from any \(z\) can be chosen from \(a,b\) . Project vertices onto the diameter of length \(D\) . If \(x\) projects to coordinate \(s\) at height \(h\) , maximality of the diameter gives \(h\le\min(s,D-s)\) . If \(z\) projects to \(t\) at height \(h_z\) , then \(d(z,x)\le h_z+|t-s|+h\le h_z+\max(t,D-t)\) , the maximum distance to the endpoints. Apply this lemma on each side of the connecting edge to obtain the four sufficient cross candidates.
Correctness¶
Skipping bypasses only edges already dark, so each query records exactly its newly dark edges. The final forest is correct. Restoring the edges first deleted by query \(i\) takes the forest from the state after query \(i\) to the state after query \(i-1\) ; initially dark edges are never restored. The merge lemma preserves every component diameter. Reverse processing only adds edges, so the global maximum can only increase. Induction proves every recorded answer.
Complexity and Contributions¶
Preprocessing, at most \(N-1\) merges, and \(M\) LCA queries take \(O((N+M)\log N)\) time and \(O(N\log N+M)\) space. The skipping structure uses path compression, and explicit traversal sequences avoid recursion on deep chains.
Codex (GPT-6) supplied this offline reverse-time method and std.cpp. The setter's centroid-decomposition idea for deletion and diameter maintenance is retained as the online alternative. Both implementations use and verify the current input specification.