/**
* Not too difficult? From the scoring section, there exists a solution with K <= n
* no matter what the tree looks like. Root the tree arbitrarily, we know that a path
* in tree is the concat. of a path going upwards, reaching a "highest" node (LCA),
* then going downwards. Therefore, a node shall determine if it should send a packet
* to the parent or a certain child.
*
* I guessed that the labelling has sth to do with subtree size. So maybe we can
* assign n to the root, meaning that the subtree rooted at it has size = n. Hmm,
* suppose that the root has 2 children, one of them has subtree size = a, the other
* has subtree size b (a+b+1=n). We can assign n-1 to a, meaning that nodes in the
* subtree of a has label <= n-1 (so we know whether we should send it upwards or
* downward), then assign n-1-b to the subtree with size b. But the problem is we
* only know the upper bound, not the lower bound!
* So, the idea is to do this in an alternating fashion based on our nodes' depth.
* The root r would be assigned 0, meaning that all nodes in this subtree has
* label >= 0. Suppose that a, b are the only children of r. We assign n-1 to a, repr.
* that all nodes in the subtree of a has labels <= n-1.
* In the routing procedure, we get all the neighbours of a node v. All neighbours
* must be in a different state as v (lower bound / upper bound?).
*
* K size: N
* Implementation 1
*/
#include <bits/stdc++.h>
#include "stations.h"
typedef std::vector<int> vec;
std::vector<vec> tree;
vec subtree;
vec labels;
void find_size(int k, int parent) {
subtree[k] = 1;
for (int child : tree[k]) {
if (child == parent)
continue;
find_size(child, k);
subtree[k] += subtree[child];
}
}
// Recursively assign labels. All nodes in the subtree
// rooted at k should have labels in [a, b].
void assign(int k, int parent, int a, int b, bool lower) {
assert(a <= b);
if (lower)
labels[k] = a++;
else
labels[k] = b--;
for (int child : tree[k]) {
if (child == parent)
continue;
assign(child, k, a, a + subtree[child] - 1, !lower);
a += subtree[child];
}
}
vec label(int n, int K, vec u, vec v) {
tree.assign(n, vec());
for (int i = 0; i < n - 1; i++) {
tree[u[i]].push_back(v[i]);
tree[v[i]].push_back(u[i]);
}
subtree.resize(n);
find_size(0, -1);
labels.resize(n);
assign(0, -1, 0, n - 1, true);
return labels;
}
int find_next_station(int s, int t, vec c) {
std::sort(c.begin(), c.end());
bool lower;
for (int neighb : c) {
if (neighb > s)
lower = true;
else
lower = false;
}
int parent = -1;
if (s != 0) {
if (lower)
parent = c.back();
else
parent = c.front();
}
if (!lower)
std::reverse(c.begin(), c.end());
for (int child : c) {
if (child == parent)
continue;
int a = s, b = child;
if (!lower)
std::swap(a, b);
if (a <= t && t <= b)
return child;
}
assert(parent != -1);
return parent;
}
