题意
给定一棵 \(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;
}