#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
void doLess(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent);
void doMore(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent);
int dp(int a,vi &parent,vector<vi> &paths,vi &s){
if(paths[a].size()==1)return 1;
for(auto u:paths[a]){
if(u==parent[a])continue;
parent[u]=a;
s[a]+=dp(u,parent,paths,s);
}
return s[a];
}
void doLess(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent){
int d=labels[a];
for(auto u:paths[a]){
if(u==parent[a])continue;
labels[u]=d-s[u];
doMore(u,labels,s,paths,parent);
d=labels[u];
}
}
void doMore(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent){
int d=labels[a];
for(auto u:paths[a]){
if(u==parent[a])continue;
labels[u]=d+s[u];
doLess(u,labels,s,paths,parent);
d=labels[u];
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
vector<vi> paths(n);
REP(i,0,n-1){
paths[u[i]].PB(v[i]);
paths[v[i]].PB(u[i]);
}
vi parent(n);
parent[0]=0;
vi s(n,1);
for(auto u:paths[0]){
parent[u]=0;
s[0]+=dp(u,parent,paths,s);
}
labels[0]=0;
int d=0;
for(auto u:paths[0]){
labels[u]=d+s[u];
doLess(u,labels,s,paths,parent);
d=labels[u];
}
//REP(i,0,n)cout<<labels[i]<<" ";
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(c.size()==1)return c[0];
if(s==0){
auto it=lower_bound(c.begin(),c.end(),t);
return *it;
}
if(c[0]>s){
int g=c.back();
c.pop_back();
if(t>c.back()||t<s)return g;
auto it=lower_bound(c.begin(),c.end(),t);
return *it;
}
if(t<c[1]||t>s)return c[0];
auto it=lower_bound(c.begin(),c.end(),t);
if(it==c.end())return c.back();
if(*it==t)return *it;
it--;
return *it;
return c[0];
}
