#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5+5;
struct node
{
int mx, sum, ind;
};
node segt[4*N];
int sub[N], ans[N], ans2[N], n;
vector<int> g[N];
void upd(int p, int val, int sm, int l = 0, int r = n-1, int pos = 1)
{
if(l==r)
segt[pos]={val,sm,p};
else
{
int mid = (l+r)/2;
if(p<=mid)
upd(p,val,sm,l,mid,pos*2);
else
upd(p,val,sm,mid+1,r,pos*2+1);
if(segt[pos*2].mx>segt[pos*2+1].mx)
segt[pos]=segt[pos*2];
else
segt[pos]=segt[pos*2+1];
segt[pos].sum=segt[pos*2].sum+segt[pos*2+1].sum;
}
}
node getmax(int lb, int rb, int l = 0, int r = n-1, int pos = 1)
{
if(rb<l||r<lb)
return {-1,0,-1};
if(lb<=l&&r<=rb)
return segt[pos];
int mid = (l+r)/2;
auto t = getmax(lb,rb,l,mid,pos*2);
auto t2 =getmax(lb,rb,mid+1,r,pos*2+1);
if(t.mx>t2.mx)
return t;
return t2;
}
node getkth(int k, int l = 0, int r = n-1, int pos = 1)
{
if(l==r)
return segt[pos];
int mid = (l+r)/2, sz = segt[pos*2].sum;
if(sz>=k)
return getkth(k,l,mid,pos*2);
return getkth(k-sz,mid+1,r,pos*2+1);
}
void dfs(int u, int p)
{
sub[u]=1;
for(auto v:g[u])
if(v!=p)
dfs(v,u),
sub[u]+=sub[v];
}
void go(int l, int r, int pos, int u, int p)
{
ans[pos]=u;
vector<int> ch;
for(auto v:g[u])
if(v!=p)
ch.pb(v);
upd(pos,-1,0);
if(ch.empty())
return;
if(ch.size()==1)
go(l,r,getmax(l,r).ind,ch[0],u);
else
{
int mid = getkth(sub[ch[0]]).ind;
go(l,mid,getmax(l,mid).ind,ch[0],u);
go(mid+1,r,getmax(mid+1,r).ind,ch[1],u);
}
}
int main()
{
fio
// ifstream cin("in.in");
cin >> n;
for(int i = 1;i<n;i++)
{
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
pair<pair<int,int>,int> p[n];
for(int i = 0;i<n;i++)
cin >> p[i].fi.fi >> p[i].fi.se,
p[i].se=i;
sort(p,p+n);
for(int i = 0;i<n;i++)
upd(i,p[i].fi.se,1);
dfs(1,1);
int st = getmax(0,n-1).ind;
go(0,n-1,st,1,1);
for(int i = 0;i<n;i++)
ans2[p[i].se]=ans[i];
for(int i = 0;i<n;i++)
cout << ans2[i] << " ";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
18412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
18412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
