#include <bits/stdc++.h> #include "stations.h" using namespace std; vector<int> in, out, labels; vector<vector<int>> g; int timer = 0; void dfs(int u, int p, bool f) { in[u] = timer++; for (auto v : g[u]) { if (v != p) { dfs(v, u, !f); } } out[u] = timer++; labels[u] = (f ? in[u] : out[u]); } vector<int> label(int n, int k, vector<int> u, vector<int> v) { g.assign(n, {}); in.assign(n, 0); out.assign(n, 0); labels.assign(n, 0); for (int i = 0; i < n - 1; i++) { g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } dfs(0, -1, 1); auto a = labels; sort(a.begin(), a.end()); for (auto &x : labels) { x = lower_bound(a.begin(), a.end(), x) - a.begin(); } return labels; } int find_next_station(int s, int t, vector<int> c) { if (c[0] > s) { if (t < s) { return c.back(); } if (t > c.back()) { return c.back(); } for (auto x : c) { if (x >= t) { return x; } } } if (t < c[0]) { return c[0]; } if (t > s) { return c[0]; } reverse(c.begin(), c.end()); for (auto x : c) { if (x <= t) { return x; } } return 0; }