#include "stations.h"
#include <vector>
#include <algorithm>
using namespace std;
// Qo'shnichilik ro'yxati va tartib raqamlari uchun o'zgaruvchilar
vector<vector<int>> adj;
vector<int> labels;
int timer;
// DFS orqali Pre-order va Post-order raqamlash
void dfs(int u, int p, int depth) {
int pre = timer++;
for (int v : adj[u]) {
if (v != p) {
dfs(v, u, depth + 1);
}
}
int post = timer++;
// Juft chuqurlikda Pre-order, toq chuqurlikda Post-order yorlig'ini beramiz
if (depth % 2 == 0) {
labels[u] = pre;
} else {
labels[u] = post;
}
}
// 1. Stansiyalarga yorliq berish funksiyasi
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
adj.assign(n, vector<int>());
for (int i = 0; i < n - 1; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
labels.resize(n);
timer = 0;
dfs(0, -1, 0);
// Yorliqlarni 0 dan n-1 gacha bo'lgan oraliqqa siqish (label uniqueness)
vector<int> sorted_labels = labels;
sort(sorted_labels.begin(), sorted_labels.end());
for (int i = 0; i < n; i++) {
labels[i] = lower_bound(sorted_labels.begin(), sorted_labels.end(), labels[i]) - sorted_labels.begin();
}
return labels;
}
// 2. Keyingi stansiyani topish funksiyasi
int find_next_station(int s, int t, vector<int> c) {
// s - hozirgi tugun, t - maqsad, c - qo'shnilar
// Agar s < c[0] bo'lsa, demak s tugunida Pre-order yorlig'i bor (juft qatlam)
if (s < c[0]) {
// Maqsad ostki daraxtda ekanligini tekshiramiz
for (int i = 0; i < (int)c.size() - 1; i++) {
int left = c[i];
int right = c[i + 1] - 1;
if (t >= left && t <= right) return c[i];
}
// Agar ostki daraxtda bo'lmasa, ota tugunga (oxirgi qo'shni) yuboramiz
return c.back();
}
// Aks holda, s tugunida Post-order yorlig'i bor (toq qatlam)
else {
// Post-order holati uchun teskari tekshiruv
for (int i = (int)c.size() - 1; i > 0; i--) {
int right = c[i];
int left = c[i - 1] + 1;
if (t >= left && t <= right) return c[i];
}
// Agar ostki daraxtda bo'lmasa, ota tugunga (birinchi qo'shni) yuboramiz
return c[0];
}
}
