#include <iostream>
#include "stations.h"
#include <vector>
bool debug=0;
using namespace std;
#define pb push_back
#define mp make_pair
vector<vector<int>> adj;
vector<int> bl; // base labels (euler search)
int cur=0;
void dfs(int node){ // used to initialise `bl`
bl[node] = cur;
cur++;
for(int e:adj[node]){
if(bl[e]==-1){
dfs(e);
}
}
return;
}
vector<int> ml; // max-labels (max bl of all children)
int get_ml(int node){
// if(ml[node]!=-1)return ml[node];
int answer=bl[node];
for(int e:adj[node]){
if(bl[e]>bl[node]){ // is that a child?
answer=max(answer, get_ml(e));
}
}
ml[node] = answer;
return ml[node];
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
bl = vector<int>(n, -1);
ml = vector<int>(n, -1);
adj = vector<vector<int>>(n);
for(int i=0; i<n-1; i++){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
cur=0;
dfs(0);
get_ml(0);
vector<int> labels(n);
for(int i=0; i<n; i++){
labels[i] = 1000*bl[i] + ml[i];
}
if(debug)
{
cout<<"$ LABELS ARE AS FOLLOWS:\n";
for(int i=0; i<n; i++){
cout<<labels[i]<<"\n";
}
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
for(int i=0; i<c.size(); i++){
if(c[i] == t){
return c[i];
}
}
int target_base = t/1000;
int this_base=s/1000, this_max=s%1000;
int next_base, next_max;
if(target_base < this_base || target_base > this_max){
// we have to travel up (towards the root)
return c[0];
} else{
// we have to travel down the tree
for(int i=0; i<c.size(); i++){
next_base = c[i]/1000;
next_max = c[i]%1000;
if(next_base < this_base)continue;// make sure it's not a parent node
if(next_base <= target_base && next_max >= target_base){
return c[i];
}
}
}
return c[0];
}
