#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5;
struct point
{
int x, y, poz;
};
int n;
vector<int> G[nmax + 5];
int w[nmax + 5];
int st[nmax + 5], dr[nmax + 5];
int rez[nmax + 5];
void get_sons(int nod, int dad = 0)
{
w[nod] = 1;
for(auto it : G[nod])
{
if(it == dad)
{
continue;
}
if(!st[nod])
{
st[nod] = it;
}
else
{
dr[nod] = it;
}
get_sons(it, nod);
w[nod] += w[it];
}
}
void dfs(int nod, point r, vector<point> l)
{
rez[r.poz] = nod;
if(!st[nod])
{
return;
}
sort(l.begin(), l.end(), [r](point a, point b)
{
long long d = (1LL * a.x * r.y + 1LL * r.x * b.y + 1LL * b.x * a.y) - (1LL * a.y * r.x + 1LL * r.y * b.x + 1LL * b.y * a.x);
return (d > 0);
});
if(!dr[nod])
{
point r_st = l.front();
vector<point> l_st;
for(int i=1;i<l.size();i++)
{
l_st.push_back(l[i]);
}
dfs(st[nod], r_st, l_st);
}
else
{
point r_st = l[w[st[nod]] - 1];
point r_dr = l[w[st[nod]]];
vector<point> l_st, l_dr;
for(int i=0;i<w[st[nod]]-1;i++)
{
l_st.push_back(l[i]);
}
for(int i=w[st[nod]]+1;i<l.size();i++)
{
l_dr.push_back(l[i]);
}
dfs(st[nod], r_st, l_st);
dfs(dr[nod], r_dr, l_dr);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n;
for(int i=1; i<n; i++)
{
int x, y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
vector<point> v;
point r = point{0, -1, 0};
for(int i=1; i<=n; i++)
{
point p;
cin>>p.x>>p.y;
p.poz = i;
v.push_back(p);
if(p.y > r.y)
{
r = p;
}
}
vector<point> aux;
for(auto it : v)
{
if(it.poz == r.poz)
{
continue;
}
aux.push_back(it);
}
v = aux;
get_sons(1);
dfs(1, r, v);
for(int i=1;i<=n;i++)
{
cout<<rez[i]<<' ';
}
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... |