CF342E Xenia and Tree

题意

给定一棵 \(n\) 个节点的一棵树，初始时 \(1\) 号点为红色，其余为蓝色。

要求支持以下操作：

• 将一个节点变为红色。
• 询问节点 \(u\) 到最近红色节点的距离

共 \(q\) 次操作。

Sol

喵喵题。

不难想到点分树做法，不再阐述。

考虑简单的操作分块。

• 对于块外，可以考虑每做完一个块就暴力 \(dp\) 重构。这部分复杂度为 \(O(q \times \sqrt n)\)。
• 对于块内，考虑暴力计算答案，用 \(O(n \log n) ~ O(1)\) lca即可。

简单提一下 \(O(n \log n) ~ O(1)\) lca。

考虑树的欧拉序列。

记 \(dfn_x\) 表示第一次访问节点 \(x\) 的时间、\(idx_{cnt}\) 表示时间为 \(cnt\) 访问的节点。

考虑两个点走过的路径，不难发现 \(min_{i = dfn_u} ^ {dfn_v} idx_i\) 即为 \(lca\) 的时间。

直接 \(st\) 表维护即可，可以使用 +1-1rmq 做到 \(O(n) ~ O(1)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 1e5 + 5, M = 2e5 + 5, inf = 2e9;

namespace G {

array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
	cnt++;
	nex[cnt] = fir[x];
	to[cnt] = y;
	fir[x] = cnt;
}

}

namespace Esl {

array <int, M> dfn, idx;
array <int, N> fa, dep;
int cnt;

void dfs(int x) {
	cnt++;
	dfn[x] = cnt;
	idx[cnt] = x;
	for (int i = G::fir[x]; i; i = G::nex[i]) {
		if (G::to[i] == fa[x]) continue;
		dep[G::to[i]] = dep[x] + 1;
		fa[G::to[i]] = x;
		dfs(G::to[i]), cnt++, idx[cnt] = x;
	}
}

array <array <int, 22>, M> sT;
array <int, M> lg;

void init() {
	for (int i = 1; i <= cnt; i++)
		lg[i] = log2(i);
	for (int i = 1; i <= cnt; i++)
		sT[i].fill(inf);
	for (int i = 1; i <= cnt; i++)
		sT[i][0] = dfn[idx[i]];
	for (int j = 1; j < 21; j++)
		for (int i = 1; i + (1 << j) - 1 <= cnt; i++)
			sT[i][j] = min(sT[i][j - 1], sT[i + (1 << (j - 1))][j - 1]);
}

int query(int _l, int _r) {
	int l = min(dfn[_l], dfn[_r]), r = max(dfn[_l], dfn[_r]), len = lg[r - l + 1];
	return idx[min(sT[l][len], sT[r - (1 << len) + 1][len])];
}

}

array <int, N> f;

void dfs1(int x) {
	for (int i = G::fir[x]; i; i = G::nex[i]) {
		if (G::to[i] == Esl::fa[x]) continue;
		dfs1(G::to[i]);
		f[x] = min(f[G::to[i]] + 1, f[x]);
	}
}

void dfs2(int x) {
	for (int i = G::fir[x]; i; i = G::nex[i]) {
		if (G::to[i] == Esl::fa[x]) continue;
		f[G::to[i]] = min(f[x] + 1, f[G::to[i]]);
		dfs2(G::to[i]);
	}
}

const int blk = 352;

void remake() { dfs1(1), dfs2(1); }

int calc(int x) {
	return (x - 1) / blk + 1;
}

array <int, N> arc;

int main() {
	int n = read(), m = read();
	for (int i = 2; i <= n; i++) {
		int x = read(), y = read();
		G::add(x, y), G::add(y, x);
	}
	f.fill(inf), f[1] = 0;
	Esl::dfs(1);
	/* puts("@"); */
	Esl::init();
	/* puts("#"); */
	remake();
	for (int i = 1; i <= m; i++) {
		int op = read(), x = read();
		arc[i] = 1;
		if (op == 1) {
			f[x] = 0;
			arc[i] = x;
		}
		else {
			int ans = f[x];
			for (int j = (calc(i) - 1) * blk + 1; j < i; j++)
				ans = min(ans, Esl::dep[x] + Esl::dep[arc[j]] - 2 * Esl::dep[Esl::query(x, arc[j])]);
			write(ans), puts("");
		}
		if (i % blk == 0) remake();
	}
	return 0;
}