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