#include<bits/stdc++.h>
#define MAXN 10007
using namespace std;
struct point{
int x,y,id;
inline friend bool operator == (point fr,point sc){
return fr.x==sc.x and fr.y==sc.y;
}
}p;
int n,root,a,b,sz[MAXN];
vector<int> v[MAXN],tree[MAXN];
int parent[MAXN],sol[MAXN];
vector<point> w;
void dfs(int x,int p){
sz[x]=1;
parent[x]=p;
for(int i:v[x]){
if(i==p)continue;
dfs(i,x);
tree[x].push_back(i);
sz[x]+=sz[i];
}
if(tree[x].size()==2 and sz[tree[x][0]]>sz[tree[x][1]])swap(tree[x][0],tree[x][1]);
}
point zero;
const double inf=1e9;
double angle(double x,double y){
if(x==0)return 0;
if(y==0){
if(x<=0)return -inf;
else return inf;
}
return x/y;
}
bool cmp(point fr,point sc){
return angle(fr.x-zero.x,fr.y-zero.y) < angle(sc.x-zero.x,sc.y-zero.y);
}
void solve(vector<point> &w,int curr){
if(w.size()==1){
sol[w[0].id]=curr;
return;
}
int mins=0;
for(int i=0;i<w.size();i++){
if(w[i].y<w[mins].y)mins=i;
}
zero=w[mins];
int ver=zero.id;
sol[ver]=curr;
if(tree[curr].size()==1){
for(int i=0;i<w.size();i++){
if(w[i]==zero){
swap(w[i],w[w.size()-1]);
w.pop_back(); break;
}
}
solve(w,tree[curr][0]);
return;
}
if(sz[tree[curr][0]]<=15){
for(int i=0;i<w.size();i++){
if(w[i]==zero){
swap(w[i],w[w.size()-1]);
w.pop_back(); break;
}
}
vector<point> l;
for(int t=0;t<sz[tree[curr][0]];t++){
point mins=w[0];
for(int i=0;i<w.size();i++){
if(angle(w[i].x-zero.x,w[i].y-zero.y)<angle(mins.x-zero.x,mins.y-zero.y)){
mins=w[i];
}
}
l.push_back(mins);
for(int i=0;i<w.size();i++){
if(w[i]==mins){
swap(w[i],w[w.size()-1]);
w.pop_back(); break;
}
}
}
solve(l,tree[curr][0]);
solve(w,tree[curr][1]);
return;
}
sort(w.begin(),w.end(),cmp);
vector<point> l,r;
for(int i=0;i<w.size();i++){
if(w[i]==zero)continue;
if(int(l.size())<sz[tree[curr][0]]){
l.push_back(w[i]);
}else{
r.push_back(w[i]);
}
}
solve(l,tree[curr][0]);
if(tree[curr].size()==2)solve(r,tree[curr][1]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=1;i<=n;i++){
if(v[i].size()<=2)root=i;
}
dfs(root,0);
for(int i=1;i<=n;i++){
cin>>p.x>>p.y;
p.id=i;
w.push_back(p);
}
solve(w,root);
for(int i=1;i<=n;i++){
cout<<sol[i]<<" ";
}
cout<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |