Codeforces 342(#199 Div2 only) E. Xenia and Tree

問題

n頂点からなる無向木が与えられる。最初1番の頂点だけが色つき。
この木に対して以下のクエリを処理せよ。


1 v : 頂点vに色をつける。
2 v : 頂点vに最も近い色つきの頂点の距離を出力する。

制約条件

n, クエリ≦100000

方針

Heavy-Light decomposition + 折れ線をsetで管理でやった。
全然想定解法と違った。当たり前だった。


頂点vに色をつけたとき、dist[v] = 0, dist[p[v]] = 1, dist[p[p[v]] = 2, ...
という風に更新することを考える。(ここでp[v]はvの親の意味)


このようにdistを持っていれば、頂点vからの距離を求めるクエリが来たとき、
距離 = min{ dist[a] + depth[v] - depth[a] | aはvの先祖 }と表すことができる。


これだと木の深い頂点ばっかりクエリが来たら死ぬので、Heavy-Light Decompositionして深さをlogくらいにする。
Heavy-Light Decompositionをすると、木が列の集合になるので、
各列の中で次のようなクエリが処理できればよい。


distを1次元の配列とする。
dist[pos] := xとする操作。
min{ dist[i] + abs(i - pos) }を求める操作。


minを求める操作は、min(min{dist[i] + i - pos | i >= pos}, min{dist[i] + pos - i | i <= pos})
と変形することができるので、min{dist[i] + i - pos | i >= pos}と min{dist[i] + pos - i | i <= pos}を別々のデータ構造を使って管理すればよさそう。


setを使って、減少列を変わり目だけ覚えておいて、dequeのやつっぽく、
同じ位置で解が悪い間eraseし続ける感じでやればよい。
(上側に来る直線を消し続ける)


で、前者と後者で二つのsetを使えばよい。


あとはH-L Decompositionした木を根のほうまで辿っていって、
最初の説明とこのクエリの操作を組み合わせたことをやればよい。

ちなみに

想定解はクエリの平方分割。
クエリをsqrt(n)個のかたまりごとに分割して考える。
各かたまりの先頭で、各頂点からの、どれでもいいから色つきの点までの最短距離を求める。
これはBFSの初期ノードに色つきの頂点を全部突っ込んでBFSすればいい。
これをdist[v]と呼ぶことにする。


で、距離を答えるクエリでは、dist[v]とmin{u, vの距離 | 今のかたまりで質問の前に色が変わる点u}のうち小さいほうを取ればよい。

ソースコード

void size_rec(int, int);
void heavy_light_rec(int, int, int);

const int MX = 100010;

struct S{
	int n;
	set<pi> s, t; //(pos, x + y), (-pos, y - x)
	S(int n):n(n){
		s.insert(mp(n - 1, inf));
		t.insert(mp(0, inf));
	}
	int get(int x){
		set<pi>::iterator it = s.lower_bound(mp(x, -inf));
		set<pi>::iterator jt = t.lower_bound(mp(-x, -inf));
		int res = it->second - x;
		res = min(res, jt->second + x);
		return res;
	}
	void add1(int x, int y){
		set<pi>::iterator it = s.lower_bound(mp(x + 1, -inf));
		if(it != s.end() && x + y > it->second) return;
		
		while(it != s.begin()){
			--it;
			if(x + y > it->second) break;
			s.erase(it);
			it = s.lower_bound(mp(x, -inf));
		}
		s.insert(mp(x, x + y));
	}
	void add2(int x, int y){
		set<pi>::iterator it = t.lower_bound(mp(x + 1, -inf));
		if(it != t.end() && x + y > it->second) return;
		
		while(it != t.begin()){
			--it;
			if(x + y > it->second) break;
			t.erase(it);
			it = t.lower_bound(mp(x + 1, -inf));
		}
		t.insert(mp(x, x + y));
	}
	void add(int x, int y){
		add1(x, y);
		add2(-x, y);
	}
};
S *data[MX];
int bkt_sz;
int bkt_root[MX];

int n, q;
int dist[MX];
int sz[MX];
int parent[MX];
int depth[MX];
int which[MX];

vector<vi> e;

int main(){
	scanf("%d%d", &n, &q);
	e.resize(n);
	
	rep(i, n - 1){
		int a, b; scanf("%d%d", &a, &b);
		a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	
	rep(i, n) dist[i] = inf;
	
	memset(which, -1, sizeof(which));
	size_rec(0, 0);
	heavy_light_rec(0, 0, -1);
	
	while(q--){
		int t, b; scanf("%d%d", &t, &b);
		b--;
		
		if(t == 1){
			int ofs = 0;
			while(1){
				int bkt = which[b];
				if(bkt < 0) dist[b] = min(dist[b], ofs);
				else{
					int pos = depth[b] - depth[bkt_root[bkt]];// dbg(pos); dbg(ofs);
					data[bkt]->add(pos, ofs);
				}
				if(b == 0 || bkt >= 0 && bkt_root[bkt] == 0) break;
				
				int pd = depth[b];
				if(bkt < 0) b = parent[b], ofs++;
				else b = parent[bkt_root[bkt]], ofs += pd - depth[b];
			}
		}
		else{
			int ans = depth[b], ofs = 0;
			while(1){
				int bkt = which[b];
				if(bkt < 0) ans = min(ans, dist[b] + ofs);
				else{
					int pos = depth[b] - depth[bkt_root[bkt]];
					ans = min(ans, data[bkt]->get(pos) + ofs);
				}
				if(b == 0 || bkt >= 0 && bkt_root[bkt] == 0) break;
				
				int pd = depth[b];
				if(bkt < 0) b = parent[b], ofs++;
				else b = parent[bkt_root[bkt]], ofs += pd - depth[b];
			}
			printf("%d\n", ans);
		}
	}
	
	return 0;
}

void size_rec(int c, int p){
	sz[c] = 1;
	depth[c] = c == p ? 0 : depth[p] + 1;
	parent[c] = p;
	rep(i, e[c].size()) if(e[c][i] != p){
		size_rec(e[c][i], c);
		sz[c] += sz[e[c][i]];
	}
}
void heavy_light_rec(int c, int p, int root){
	
	bool found = 0;
	
	rep(i, e[c].size()){
		int to = e[c][i];
		if(to == p) continue;
		
		if(2 * sz[to] >= sz[c]){
			heavy_light_rec(to, c, root < 0 ? c : root);
			found = 1;
		}
		else heavy_light_rec(to, c, -1);
	}
	if(!found && root >= 0){
		int size = depth[c] - depth[root] + 1;
		bkt_root[bkt_sz] = root;
		data[bkt_sz] = new S(size);
		
		for(int v = c; ; v = parent[v]){
			which[v] = bkt_sz;
			if(v == root) break;
		}
		bkt_sz++;
	}
}