UTPC2013 I 支配と友好

問題

日本語なので本文参照(http://utpc2013.contest.atcoder.jp/tasks/utpc2013_09
根つき木が与えられる。
各頂点には数字がついている。


それぞれの頂点に対して、
自分の親でも子でもない頂点のうち、自分に最も数字が近い頂点の数字を答えよ。
複数ある場合は小さいほうを答えよ。

制約条件

頂点≦10^5
数字≦10^9

方針

segment木を使う解法のほうが自分は断然好きなのだけど、
想定解は二回オイラーツアーをやるというもの。


オイラーツアーをやっていって、前に出た頂点のうち、二度出たものは、
それは親でも子でもないので、近い数字の候補になる。


で、こいつは左側のほうしか見てないので、オイラーツアーを逆順にやって、
右側でも近い数字を見る。
二つのうち近いほうが答え。


沢山の数字の中から自分に一番近いものを探すのはsetを使えばいい。


なので、終わった頂点だけsetに入れながら、2回オイラーツアーをすればいい。

const int MX = 100000;
int n, a[MX];
vector<vi> e;
set<int> s;
 
int ans[MX];
bool notroot[MX];
 
inline int select(int a, int b, int value){
	if(a < 0) return b;
	if(b < 0) return a;
	if(abs(a - value) < abs(b - value)) return a;
	if(abs(b - value) < abs(a - value)) return b;
	return a < b ? a : b;
}
int get(int value){
	set<int>::iterator it = s.lower_bound(value);
	int ans = it != s.end() ? *it : -1;
	
	if(it != s.begin()){
		--it;
		ans = select(ans, *it, value);
	}
	return ans;
}
 
void dfs(int c){
	ans[c] = select(ans[c], get(a[c]), a[c]);
	rep(i, e[c].size()) dfs(e[c][i]);
	s.insert(a[c]);
}
 
int main(){
	cin >> n;
	e.resize(n);
	
	rep(i, n) cin >> a[i];
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		e[a].pb(b);
		notroot[b] = 1;
	}
	int root = 0;
	for(; notroot[root]; root++);
	
	memset(ans, -1, sizeof(ans));
	
	dfs(root);
	rep(i, n) reverse(all(e[i]));
	
	s.clear();
	dfs(root);
	
	rep(i, n) cout << ans[i] << endl;
	
	return 0;
}