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; }