#include "stations.h" #include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<int(n);i++) using namespace std; typedef long long ll; static vector<vector<int>>E; static vector<int>labels; static int cnt=0; void dfs(int v,int p){ int x=0; int d=0; for(int u:E[v]){ if(u==p)continue; dfs(u,v); x|=labels[u]; d++; } if(d<=1){ x|=1<<cnt; cnt++; } labels[v]=x; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){ E=vector<vector<int>>(n); labels=vector<int>(n); cnt=0; vector<int>deg(n); rep(i,n-1){ E[u[i]].push_back(v[i]); E[v[i]].push_back(u[i]); deg[u[i]]++; deg[v[i]]++; } dfs(0,-1); return labels; } int find_next_station(int s, int t, std::vector<int> c) { for(int u:c){ if((s|u)==u)continue; if((t|u)==u)return u; } for(int u:c){ if((s|u)==u)return u; } return -1; }