One Secret Shortcut
National Olympiad — National round (2014 season)
Submission name: tripat.cpp
Problem summary
A weighted tree is rooted at 1. For each independent query, travel from 1 to A and then B. Before that trip, one new undirected edge of weight T may be placed between any two distinct vertices. Find the minimum possible travel time; the edge may be used more than once.
Input
N; for vertices i=2..N, parent P[i] and edge weight C[i]; Q; then Q triples A B T.
Output
One minimum travel time per query.
Constraints
2≤N≤1000000; 1≤Q≤100000; 0≤C[i]≤1000; 0≤T≤1000000; 2≤A,B≤N; A≠B.
Worked example
An independently prepared example for this explanation.
Input
4 1 4 2 3 2 5 2 3 4 1 4 3 10
Output
8 17
Solution analysis
- Let da=dist(1,A), db=dist(1,B) and dab=dist(A,B). The answer is the minimum of da+dab, da+T, T+dab, and 2T+db. These represent no shortcut, a shortcut A–B used once, a shortcut 1–A used once, and that same shortcut used twice.
- To see completeness, a shortest route for either trip leg uses the extra edge at most once. If it is used by one leg, its cost is at least T, giving one of the middle bounds. If both legs use it in the same orientation, deleting the two shortcut traversals leaves at least dist(1,B) worth of tree travel; if orientations differ, the remaining tree portions also connect 1 to B. Hence 2T+db is a lower bound for using it twice and is attained by placing it at 1–A.
- Compute distances with LCA: dab=da+db−2dist(1,LCA(A,B)). Heavy-light chain heads give O(log N) LCA queries with linear memory. In the sample, T=1 permits the trip 1→2→3 followed by the new edge 3–4, total 8. With T=10 the best route remains entirely in the tree, total 17.
Why it works
The unique tree paths give the no-shortcut cost. A shortest path for each leg is simple and uses a new edge at most once. One use costs at least T plus the untouched leg; two uses cost at least 2T plus a collection of tree walks connecting 1 and B. Each of these bounds is attained by the placements described, so the minimum formula is exact. LCA computes the required original tree distance.
Watch out. The shortcut can be used twice and can be ignored. Use 64-bit sums. Parent labels need not be smaller than child labels, so derive traversal order from the supplied parent tree.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Let da=dist(1,A), db=dist(1,B) and dab=dist(A,B).
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count;
cin>>count;
vector<int>parent(count+1,0),head(count+1,0),next(count+1,0);
vector<int>subtree(count+1,0),depth(count+1,0);
for(int vertex=2;vertex<=count;vertex++){
cin>>parent[vertex]>>subtree[vertex];
next[vertex]=head[parent[vertex]];
head[parent[vertex]]=vertex;
}
vector<int>order;
order.reserve(count);
order.push_back(1);
vector<long long>distance(count+1,0);
for(size_t index=0;index<order.size();index++){
int vertex=order[index];
for(int child=head[vertex];child!=0;child=next[child]){
distance[child]=distance[vertex]+subtree[child];
depth[child]=depth[vertex]+1;
order.push_back(child);
}
}
vector<int>heavy(count+1,0),chain(count+1,0);
for(int index=count-1;index>=0;index--){
int vertex=order[index];
subtree[vertex]=1;
for(int child=head[vertex];child!=0;child=next[child]){
subtree[vertex]+=subtree[child];
if(subtree[child]>subtree[heavy[vertex]]){
heavy[vertex]=child;
}
}
}
chain[1]=1;
for(size_t index=1;index<order.size();index++){
int vertex=order[index];
chain[vertex]=heavy[parent[vertex]]==vertex?chain[parent[vertex]]:vertex;
}
auto lca=[&](int a,int b){
while(chain[a]!=chain[b]){
if(depth[chain[a]]<depth[chain[b]]){
swap(a,b);
}
a=parent[chain[a]];
}
return depth[a]<depth[b]?a:b;
};
int queries;
cin>>queries;
while(queries--){
int a,b;
long long shortcut;
cin>>a>>b>>shortcut;
long long between=distance[a]+distance[b]-2*distance[lca(a,b)];
long long answer=min(
{distance[a]+between,distance[a]+shortcut,shortcut+between,2*shortcut+distance[b]});
cout<<answer<<'\n';
}
}