Diameters after Roads Are Removed
Autumn Tournament (2015)
Submission name: roads.cpp
Problem summary
A weighted tree has N cities. Its N−1 roads are listed in construction order. Convert roads into unusable highways in that same order. Each removal splits one current component into two. Report the diameter lengths of precisely those two new components, sorted increasingly.
Input
N, followed by N−1 lines u v length in removal order.
Output
For each removal print the two resulting component diameters in nondecreasing order. A one-vertex component has diameter zero.
Constraints
2 ≤ N ≤ 500000; every road length is an integer between 1 and 1000.
Worked example
Official sample, with spacing restored from the PDF. The first cut leaves paths of lengths 3 on both sides.
Input
5 1 2 2 2 3 1 2 4 2 1 5 3
Output
3 3 0 2 0 0 0 0
Solution analysis
- Deletion is awkward for a disjoint-set union structure, but reversing time turns every deletion into an addition. Begin with N isolated cities and restore roads from the last input line to the first. Immediately before restoring a road, its two DSU components are exactly the two components whose diameters the corresponding forward removal asks for.
- Store one diameter endpoint pair and its length for every component. When components with endpoints (a,b) and (c,d) are connected, their new diameter is either an old diameter or one of the four paths a–c, a–d, b–c, b–d. A farthest vertex from any attachment point in a tree can always be chosen among a diameter’s endpoints.
- All distance queries can use the original full tree: its unique path between vertices of a restored component contains only restored roads. Preprocess depths, root distances and binary-lifting ancestors once, then distance(u,v)=rootDistance[u]+rootDistance[v]−2·rootDistance[LCA(u,v)]. Use an iterative traversal because a path can contain half a million vertices.
- For the sample, reverse time first restores 1–5, then 2–4, then 2–3, then 1–2. Before the final restoration the two component diameters are 3 and 3, so the first forward output is 3 3. Store answers by the original edge index and print them forwards.
Why it works
At each reverse step DSU represents exactly the graph remaining immediately after the corresponding forward removal. Any new path either lies in an old component or crosses the restored road once. In the latter case its maximum possible length uses farthest vertices from the attachment points, which can be chosen among each component’s stored diameter endpoints. Testing the four endpoint pairs and old diameters therefore preserves the diameter invariant and proves every saved answer.
Watch out. Report only the two components being split, not all existing components. Save their diameters before merging in reverse time. Keep weighted distances separate from unweighted depths used by LCA. Avoid recursive DFS on long paths.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<numeric>
#include<utility>
#include<vector>
using namespace std;
struct Edge{
int u,v,weight;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<Edge>edges(n-1);
vector<vector<pair<int,int>>>graph(n+1);
for(auto&edge:edges){
cin>>edge.u>>edge.v>>edge.weight;
graph[edge.u].push_back({edge.v,edge.weight});
graph[edge.v].push_back({edge.u,edge.weight});
}
int levels=1;
while((1<<levels)<=n){
levels++;
}
vector<vector<int>>up(levels,vector<int>(n+1));
vector<int>depth(n+1),order{1};
vector<long long>rootDistance(n+1);
for(int i=0;i<n;i++){
int v=order[i];
for(auto[to,weight]:graph[v]){
if(to==up[0][v]){
continue;
}
up[0][to]=v;
depth[to]=depth[v]+1;
rootDistance[to]=rootDistance[v]+weight;
order.push_back(to);
}
}
for(int level=1;level<levels;level++){
for(int v=1;v<=n;v++){
up[level][v]=up[level-1][up[level-1][v]];
}
}
auto distance=[&](int a,int b){
long long sum=rootDistance[a]+rootDistance[b];
if(depth[a]<depth[b]){
swap(a,b);
}
int difference=depth[a]-depth[b];
for(int level=0;level<levels;level++){
if((difference>>level)&1){
a=up[level][a];
}
}
if(a!=b){
for(int level=levels-1;level>=0;level--){
if(up[level][a]!=up[level][b]){
a=up[level][a];
b=up[level][b];
}
}
a=up[0][a];
}
return sum-2*rootDistance[a];
};
vector<int>parent(n+1),size(n+1,1),first(n+1),second(n+1);
iota(parent.begin(),parent.end(),0);
iota(first.begin(),first.end(),0);
iota(second.begin(),second.end(),0);
vector<long long>diameter(n+1);
vector<pair<long long,long long>>answer(n-1);
auto find=[&](int v){
int root=v;
while(root!=parent[root]){
root=parent[root];
}
while(v!=root){
int next=parent[v];
parent[v]=root;
v=next;
}
return root;
};
for(int i=n-2;i>=0;i--){
int a=find(edges[i].u);
int b=find(edges[i].v);
answer[i]=minmax(diameter[a],diameter[b]);
int bestFirst=first[a],bestSecond=second[a];
long long best=diameter[a];
if(diameter[b]>best){
best=diameter[b];
bestFirst=first[b];
bestSecond=second[b];
}
// A longest new path uses diameter endpoints of the old components.
for(int x:{first[a],second[a]}){
for(int y:{first[b],second[b]}){
long long candidate=distance(x,y);
if(candidate>best){
best=candidate;
bestFirst=x;
bestSecond=y;
}
}
}
if(size[a]<size[b]){
swap(a,b);
}
parent[b]=a;
size[a]+=size[b];
diameter[a]=best;
first[a]=bestFirst;
second[a]=bestSecond;
}
for(auto[a,b]:answer){
cout<<a<<' '<<b<<'\n';
}
}