IJPC #1 A - Innocent Animals and Destruction of Forests

問題文 : むこのどうぶつたち と しんりんのはかい

解法 :

分離されていく部分木の大きさを, クエリあたり大体$O(\log N)$ で求められるとうれしい.
クエリが先読みできれば, union-find 木で逆順にたどるだけで簡単に解けるが, これはオンラインクエリなのでそう簡単にいかない.

木 + クエリ の問題の鉄則は根付き木にすることなので, この問題でもそれを実施しよう. (根はどこでもいい)
頂点を消していくと, 複数の木ができていくことが想像できる(森ができる). この問題は, その森達のうち, もっとも大きさが大きいものを答える問題と言い換えることができる.

すると, ある頂点$v$を壊すクエリが来たとき, $v$ の子たちの大きさを, 森の各木の大きさを管理するデータ構造(同じ大きさがありうるのでmultiset が適する)に突っ込み, $v$ が含まれていた木の大きさをちょっと変えてやれば良い($v$ がその木の根かどうかで処理が若干変わるので注意).

また, ある頂点$v$の根を答えるクエリは, range-max segment tree を用いることで高速に答えることができる.

分離の回数がたかだか$O(N)$ なので, 計算回数はクエリに依存せず$O(N \log N)$ となる.

コード :

#include "animals.h"
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<int> G[100000];
int depth[100000], size[100000], par[100000];
int ord[100000], dst[100000], rev[200000], time;
int ordBIT[200001], dstBIT[200001];
multiset<int> sizes;

void dfs(int v, int p)
{
	par[v] = p;
	size[v] = 1;
	rev[time] = v;
	ord[v] = time++;
	
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i] != p){
			dfs(G[v][i], v);
			size[v] += size[G[v][i]];
		}
	}
	dst[v] = time++;
}

void add(int *bit, int pos, int val)
{
	pos += 1;
	for (; pos <= 200000; pos += pos & -pos) bit[pos] += val;
}

int sum(int *bit, int pos)
{
	int ret = 0;
	pos += 1;
	for (; pos != 0; pos -= pos & -pos) ret += bit[pos];
	return (ret);
}

int seg[1 << 19], lazy[1 << 19];

void eval(int k)
{
	seg[k] = max(seg[k], lazy[k]);
	if (k < (1 << 18) - 1){
		lazy[k * 2 + 1] = max(lazy[k * 2 + 1], lazy[k]);
		lazy[k * 2 + 2] = max(lazy[k * 2 + 2], lazy[k]);
	}
	lazy[k] = 0;
}

void updateNode(int k)
{
	seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
}

void changeMax(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 18)
{
	eval(k);
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		lazy[k] = max(lazy[k], x);
		eval(k);
		return;
	}
	
	changeMax(a, b, x, k * 2 + 1, l, l + r >> 1);
	changeMax(a, b, x, k * 2 + 2, l + r >> 1, r);
	updateNode(k);
}

int get(int a, int k = 0, int l = 0, int r = 1 << 18)
{	
	eval(k);
	if (a + 1 <= l || r <= a) return (-1);
	
	if (a <= l && r <= a + 1){
		return (seg[k]);
	}
	
	int lch = get(a, k * 2 + 1, l, l + r >> 1);
	int rch = get(a, k * 2 + 2, l + r >> 1, r);
	updateNode(k);
	return (max(lch, rch));
}

void init(int N, int E[][2])
{
	for (int i = 0; i < N - 1; i++){
		G[E[i][0]].push_back(E[i][1]);
		G[E[i][1]].push_back(E[i][0]);
	}
	dfs(0, -1);
	
	sizes.insert(N);
}

int getSize(int v)
{
	return (size[v] - sum(ordBIT, ord[v]) + sum(dstBIT, dst[v]));
}

int query(int v)
{	
	int pv = rev[get(ord[v])];
	int sz = getSize(pv), sz2 = getSize(v);
	
	multiset<int>::iterator it = sizes.lower_bound(sz);
	sizes.erase(it);
	
	add(ordBIT, ord[pv], sz2);
	add(ordBIT, ord[v] + 1, -sz2);
	add(dstBIT, ord[pv], sz2);
	add(dstBIT, ord[v] + 1, -sz2);
	
	if (pv != v) sizes.insert(getSize(pv));
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i] == par[v]) continue;
		sizes.insert(getSize(G[v][i]));
		changeMax(ord[G[v][i]], dst[G[v][i]] + 1, ord[G[v][i]]);
	}
	
	it = sizes.end();
	return (*--it);
}