Submission #1555796

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1000000005
#define N 100005

int n;
int num[N];
int ans[N], lf[N], ri[N];
vector<int> arr;
vector<int> tree[N];

//seg tree data
multiset<int> data[1<<18];
int sz;

void tour(int v){
  lf[v] = arr.size();
  arr.pb(num[v]);
  for(auto to : tree[v]) tour(to);
  ri[v] = arr.size();
}

inline void del(int x, int p){
  x += sz-1;
  data[x].erase(data[x].lower_bound(p));
  while(x>0){
    x = (x-1)/2;
    data[x].erase(data[x].lower_bound(p));
  }
}

inline void ins(int x, int p){
  x += sz-1;
  data[x].insert(p);
  while(x>0){
    x = (x-1)/2;
    data[x].insert(p);
  }
}

inline void upd(int &l, const int r, const int x){
  int dl = abs(l-x), dr=abs(r-x);
  if(dl==dr && r<l) l = r;
  if(dl > dr) l = r;
}

int query(int a, int b, int x, int k, int l, int r){
  if(r<=a || b<=l) return -INF;
  if(a<=l && r<=b){
    auto itr = data[k].lower_bound(x);
    int ret = -INF;
    if(itr != data[k].end()) upd(ret, *itr,  x);
    if(itr != data[k].begin()) upd(ret, *(--itr), x);
    return ret;
  }
  int vl = query(a,b,x,k*2+1,l,(r+l)/2);
  int vr = query(a,b,x,k*2+2,(r+l)/2,r);
  int ret = -INF;
  upd(ret, vl, x);
  upd(ret, vr, x);
  return ret;
}

inline int query(int a, int b, int x){
  return query(a,b,x,0,0,sz);
}

void dfs(int v){
  int x  = num[v];
  int v1 = query(0, lf[v], x);
  int v2 = query(ri[v], n, x);

  ans[v] = -INF;
  upd(ans[v], v1, x);
  upd(ans[v], v2, x);

  if(tree[v].size()>0){
    del(lf[v], x);
    for(auto to : tree[v]) dfs(to);
    ins(lf[v], x);
  }
}

int main(){
  cin>>n;
  vector<int> par(n, -1);
  rep(i,n) cin>>num[i];

  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    tree[a].pb(b);
    par[b] = a;
  }

  int root = -1;
  rep(i,n) if(par[i] == -1) root = i;

  tour(root);

  sz=1;
  while(sz<n) sz*=2;
  rep(i,n) data[i+sz-1].insert(arr[i]);
  for(int i=sz-2; i>=0; i--){
    data[i] = data[2*i+1];
    for(auto x : data[2*i+2]) data[i].insert(x);
  }

  dfs(root);

  rep(i,n) if(ans[i]==2*INF || ans[i]==-INF) ans[i] = -1;
  rep(i,n) cout << ans[i] << endl;

  return 0;
}

Submission Info

Judge Result