Rooms at a Given Distance
National Olympiad — National round (2011 season)
Submission name: maze.cpp
Problem summary
A labyrinth is an undirected tree. For every query (v,d), output any vertex exactly d edges from v, or 0 if none exists.
Input
N; then N adjacency lists, each beginning with its length. Then Q and Q pairs v d.
Output
One suitable room number per query, or 0. Any valid room is accepted.
Constraints
5 ≤ N ≤ 20000; 1 ≤ Q ≤ 50000; d > 0.
Worked example
An independently prepared example for this explanation.
Input
8 1 5 3 7 6 5 3 4 8 5 1 3 3 2 1 3 1 2 1 2 1 3 5 3 3 8 2 7 4 2 4 3 1
Output
7 5 8 0 8
Solution analysis
- Find diameter endpoints A and B with two breadth-first searches. For every vertex v, at least one of A and B is a farthest vertex from v. A room at distance d exists exactly when max(distA[v],distB[v])≥d.
- Root the tree once at A and once at B. Build ancestor doubling tables for both roots. If distA[v]≥d, climb d parent steps toward A; otherwise, if distB[v]≥d, climb toward B.
- In the sample query (2,4) has no answer because its eccentricity is only three. Query (7,4) can follow the diameter path to room 8. Other queries may legitimately produce different answers from the printed sample.
Why it works
For any tree diameter endpoints A,B, the farthest distance from v equals max(dist(v,A),dist(v,B)). This follows by projecting v and any candidate vertex onto the diameter: an off-diameter branch cannot extend farther than both diameter endpoints without producing a longer diameter. Thus a suitable endpoint is at distance at least d exactly when an answer exists. The d-th ancestor in its rooted tree lies on the unique path and has distance exactly d.
Watch out. The printed sample is only one valid output. Use iterative BFS to avoid deep recursion, and reject d larger than both endpoint distances before climbing.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct RootedTree{
vector<int>depth;
vector<vector<int>>up;
RootedTree(const vector<vector<int>>&graph,int root){
int n=static_cast<int>(graph.size());
int levels=1;
while((1<<levels)<=n){
levels++;
}
depth.assign(n,-1);
up.assign(levels,vector<int>(n,root));
queue<int>pending;
pending.push(root);
depth[root]=0;
while(!pending.empty()){
int v=pending.front();
pending.pop();
for(int u:graph[v]){
if(depth[u]==-1){
depth[u]=depth[v]+1;
up[0][u]=v;
pending.push(u);
}
}
}
for(int bit=1;bit<levels;bit++){
for(int v=0;v<n;v++){
up[bit][v]=up[bit-1][up[bit-1][v]];
}
}
}
int farthest()const{
return static_cast<int>(max_element(depth.begin(),depth.end())-depth.begin());
}
int climb(int v,int distance)const{
for(size_t bit=0;bit<up.size();bit++){
if((distance>>bit)&1){
v=up[bit][v];
}
}
return v;
}
};
int main(){
// Compute the exact archive answer using the method explained above.
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>graph(n);
for(auto&neighbors:graph){
int count;
cin>>count;
neighbors.resize(count);
for(int&v:neighbors){
cin>>v;
v--;
}
}
int a=RootedTree(graph,0).farthest();
RootedTree fromA(graph,a);
int b=fromA.farthest();
RootedTree fromB(graph,b);
int queries;
cin>>queries;
while(queries--){
int v,distance;
cin>>v>>distance;
v--;
if(fromA.depth[v]>=distance){
cout<<fromA.climb(v,distance)+1<<'\n';
}
else if(fromB.depth[v]>=distance){
cout<<fromB.climb(v,distance)+1<<'\n';
}
else{
cout<<0<<'\n';
}
}
}