Disjoint Equal Excursions
National Olympiad — Regional round (2019 season)
Submission name: eksk.cpp
Problem summary
In a tree, choose two vertex-disjoint simple routes starting at A and B. Both routes must contain the same number of vertices. Maximize that common number.
Input
N, then N−1 edges, then A B.
Output
The largest common number of visited vertices.
Constraints
2 ≤ N ≤ 200,000; A≠B.
Worked example
An independently prepared example for this explanation.
Input
6 1 2 2 3 3 4 4 5 5 6 4 5
Output
2
Solution analysis
- Find the unique A-to-B path. For each path vertex i, compute the greatest number h[i] of edges in a branch leaving this path, or zero if no branch exists. The branches are disjoint and can be traversed in total linear time.
- If the separating path edge is between i and i+1, the longest route from A confined to its side has max(j+h[j]+1) over j≤i, numbering path positions from zero. A prefix maximum computes all these values. A reverse suffix maximum similarly gives the longest B-route on the other side.
- For each separating edge take the minimum of the two longest route lengths; a longer route can always be shortened at its end. In the six-vertex path with A=4 and B=5, cutting their shared edge leaves maximum lengths 4 and 2, so both can visit 2 villages.
Why it works
Any two disjoint connected routes have at least one unused edge on the A-to-B path between them. Cutting such an edge separates the two routes. On either side a route from its start follows the main path to some vertex and then at most one off-path branch, giving exactly the prefix or suffix formula. These maxima are achievable and truncatable to any smaller positive length. Maximizing their minimum over cuts therefore bounds and attains every possible solution.
Watch out. Count vertices, including the starting village. Off-path branch depth counts edges. Avoid recursive DFS on a 200,000-vertex chain.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
// Algorithm: Find the unique A-to-B path.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>adjacent(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adjacent[u].push_back(v);
adjacent[v].push_back(u);
}
int a,b;
cin>>a>>b;
vector<int>parent(n+1,-1),order(1,a);
parent[a]=0;
for(int i=0;i<static_cast<int>(order.size());i++){
int u=order[i];
for(int v:adjacent[u]){
if(v!=parent[u]){
parent[v]=u;
order.push_back(v);
}
}
}
vector<int>path;
for(int u=b;u!=0;u=parent[u]){
path.push_back(u);
}
reverse(path.begin(),path.end());
vector<bool>onPath(n+1,false);
for(int u:path){
onPath[u]=true;
}
int length=static_cast<int>(path.size());
vector<int>height(length),depth(n+1),previous(n+1);
for(int i=0;i<length;i++){
vector<int>stack(1,path[i]);
previous[path[i]]=0;
while(!stack.empty()){
int u=stack.back();
stack.pop_back();
height[i]=max(height[i],depth[u]);
for(int v:adjacent[u]){
if(onPath[v]||v==previous[u]){
continue;
}
previous[v]=u;
depth[v]=depth[u]+1;
stack.push_back(v);
}
}
}
vector<int>left(length),right(length);
for(int i=0;i<length;i++){
left[i]=max(i?left[i-1]:0,i+height[i]+1);
}
for(int i=length-1;i>=0;i--){
right[i]=max(i+1<length?right[i+1]:0,length-i+height[i]);
}
int answer=0;
for(int i=0;i+1<length;i++){
answer=max(answer,min(left[i],right[i+1]));
}
cout<<answer<<'\n';
}