UTPC 2013 : I - 支配と友好

む、これは頑張れば本番解けたかも…？
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_09

問題

根付き木が与えられ、各頂点には数字が割り振られている。
各頂点に対し、その子孫でも祖先でもない頂点のうち、数字が一番近いものを求めよ。

解法

Euler-tourを行い、各頂点を抜ける際に自分の数字を通過した頂点のリストに追加していく。
各頂点に入る際、そこまでに構築したリストのうちlower_boundを使いもっとも近い数字を求めればよい。

なお、木の左側からたどるEuler-tourでは、各頂点の左側にある点の数字しかlower_boundの探索最小にならない。
よって左側からたどるEuler-tourと右側からたどるEuler-tourで２回探索すればよい。

int N;
int A[100001];
int ret[100001],inin[100001];
vector<int> E[100001];
set<int> S;

void dfs(int cur,int dir) {
	
	set<int>::iterator sit=S.lower_bound(A[cur]);
	if(sit!=S.end()) {
		if(ret[cur]==-1) ret[cur]=*sit;
		if(abs(A[cur]-*sit) < abs(A[cur]-ret[cur])) ret[cur]=*sit;
		if(abs(A[cur]-*sit) == abs(A[cur]-ret[cur])) ret[cur]=min(ret[cur],*sit);
	}
	if(sit!=S.begin()) {
		sit--;
		if(abs(A[cur]-*sit) < abs(A[cur]-ret[cur])) ret[cur]=*sit;
		if(abs(A[cur]-*sit) == abs(A[cur]-ret[cur])) ret[cur]=min(ret[cur],*sit);
	}
	
	int i;
	if(dir==0) {
		FOR(i,E[cur].size()) dfs(E[cur][i],0);
	}
	else {
		FOR(i,E[cur].size()) dfs(E[cur][E[cur].size()-1-i],1);
	}
	
	S.insert(A[cur]);
}


void solve() {
	int f,i,j,k,l,x,y;
	
	MINUS(ret);
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		inin[y]++;
	}
	FOR(i,N) if(inin[i]==0) break;
	
	
	dfs(i,0);
	S.clear();
	dfs(i,1);
	
	FOR(i,N) _P("%d\n",ret[i]);
}

まとめ

Euler-tourを子孫でも先祖でもない頂点を求めるのに使うってのは、覚えておいて損のないテクかな。