# World Codesprint 10: Node-Point Mappings

### 解法

これを再帰的に繰り返すことでかならず構築できる。

#include <iostream>
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
#include <complex>

using P = std::complex<long long>;

long long cross(const P &a, const P &b) {
return imag(conj(a) * b);
}

std::vector<std::vector<int>> tree(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
return tree;
}

std::vector<P> points(n);
for (int i = 0; i < n; i++) {
long long x, y;
scanf("%lld %lld", &x, &y);
points[i].real(x);
points[i].imag(y);
}
return points;
}

int main() {
int n;
std::cin >> n;

std::vector<P> map(n);
std::vector<int> size(n);

std::function<void(int, int)> dfs = [&](int u, int p) {
size[u] = 1;
for (int v : tree[u]) {
if (v != p) {
dfs(v, u);
size[u] += size[v];
}
}
};
dfs(0, -1);

std::function<void(int, int, std::vector<P>)> dfs2 = [&](int u, int p, std::vector<P> ps) {
auto it = min_element(ps.begin(), ps.end(), [&](const P &a, const P &b) {
return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
});
P min = *it;
ps.erase(it);
std::sort(ps.begin(), ps.end(), [&](const P &a, const P &b) {
return cross(a - min, b - min) < 0;
});
map[u] = min;

int k = 0;
for (int i = 0; i < tree[u].size(); i++) {
const int v = tree[u][i];
if (v == p) {
continue;
}
std::vector<P> next;
for (int j = 0; j < size[v]; j++) {
next.push_back(ps[k++]);
}
dfs2(v, u, next);
}
};
dfs2(0, -1, points);

for (int i = 0; i < n; i++) {
int j = std::find(points.begin(), points.end(), map[i]) - points.begin();
std::cout << j + 1 << " ";
}
}