#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
vector<vector<int>> adj;
vector<int> lvl, lbl;
int currentLabel;
void DFS(int index, int last)
{
lvl[index] = lvl[last] + 1;
if (lvl[index]%2==0)
{
// Maximum node
lbl[index] = currentLabel--;
}
for (auto node : adj[index])
{
if (node == last) continue;
DFS(node, index);
}
if (lvl[index]%2)
{
// Minimum node
lbl[index] = currentLabel--;
}
}
vector<int> label(int N, int K, vector<int> U, vector<int> V)
{
// Alternate labeling (max and min subtree size)
adj = vector<vector<int>>(N);
lvl = vector<int>(N);
lbl = vector<int>(N);
for (int i = 0; i < N - 1; i++)
{
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
currentLabel = N - 1;
DFS(0, 0);
return lbl;
}
int find_next_station(int S, int T, vector<int> C)
{
if (C.size()==1)
return C[0];
if (S > C[0])
{
// Max node
// Find largest smaller than T
if (T > S || T <= C[0])
return C[0];
int l = 1, r = C.size() - 1;
while (l<r)
{
int c = (l+r+1)/2;
if (C[c] <= T)
l = c;
else
r = c - 1;
}
return C[l];
}
else
{
// Min node
if (T < S || T >= C.back())
return C.back();
// Find smallest larger than T
int l = 0, r = C.size() - 2;
while (l<r)
{
int c = (l+r)/2;
if (C[c] >= T)
r = c;
else
l = c + 1;
}
return C[l];
}
}
