QTREE5
HHH6666666666
·
·
题解
一个只需要树剖的 O(nlog^3n) 做法，但常数比 LCT 小所以跑得不慢，可以通过，且实现难度小于 LCT。
树上两点间最短距离为 depth_u+depth_v-2 \times depth_{lca(u, v)}，因此思路是对于每个点 u 维护
直接树剖建线段树维护。当一个点的颜色变化时需要将其到根的路径进行对应修改。黑转白时用其深度更新，白转黑时相当于要撤销转白。不难想到给每个节点开一个集合来带删维护最小值。把节点中的集合看作懒标记，由于删除操作均为撤销之前的某个添加操作，所有标记在被撤销时都出现在添加时的原位上，类似扫描线维护矩阵面积并的线段树。因此可以无需 `pushdown`，查询时类似标记永久化计算影响即可。实现细节见代码。
```cpp
#include<bits/stdc++.h>
#define ep emplace
#define eb emplace_back
using namespace std;
const int MAXN = 1e5 + 10;
int n, q;
vector<int> to[MAXN];
struct Segment {
int l, r;
multiset<int> s;
int min, depth;
} a[MAXN * 4];
int pa[MAXN], depth[MAXN], siz[MAXN], hson[MAXN];
int top[MAXN], dfn[MAXN], rk[MAXN], timecnt;
int co[MAXN];
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((a[p].l + a[p].r) >> 1)
void pushup(int p) {
a[p].min = 1e6;
if (a[p].l != a[p].r) a[p].min = min(a[ls].min, a[rs].min), a[p].depth = max(a[ls].depth, a[rs].depth);
if (a[p].s.size()) a[p].min = min(a[p].min, *a[p].s.begin() - 2 * a[p].depth);
return;
}
void build(int p, int l, int r) {
a[p].l = l, a[p].r = r;
if (l == r) {
a[p].depth = depth[rk[l]];
a[p].min = 1e6;
return;
}
build(ls, l, mid), build(rs, mid + 1, r);
pushup(p);
return;
}
void modify(int p, int l, int r, int k, bool t) {
if (l <= a[p].l && a[p].r <= r) {
if (!t) a[p].s.ep(k);
else a[p].s.erase(a[p].s.find(k));
pushup(p); return;
}
if (l <= mid) modify(ls, l, r, k, t);
if (mid < r) modify(rs, l, r, k, t);
pushup(p);
return;
}
int query(int p, int l, int r) {
if (l <= a[p].l && a[p].r <= r) return a[p].min;
int res = 1e6;
if (a[p].s.size()) res = min(res, *a[p].s.begin() - 2 * depth[rk[r]]);
if (l <= mid) res = min(res, query(ls, l, r));
if (mid < r) res = min(res, query(rs, l, r));
return res;
}
#undef ls
#undef rs
#undef mid
void buildtree(int x, int parent) {
pa[x] = parent, depth[x] = depth[pa[x]] + 1, siz[x] = 1;
for (int y : to[x]) {
if (y == pa[x]) continue;
buildtree(y, x), siz[x] += siz[y];
if (siz[y] > siz[hson[x]]) hson[x] = y;
}
return;
}
void decompose(int x, int t) {
top[x] = t, dfn[x] = ++timecnt, rk[timecnt] = x;
if (hson[x]) decompose(hson[x], t);
for (int y : to[x])
if (!dfn[y]) decompose(y, y);
return;
}
void modifypath(int x, int t) {
int d = depth[x];
while (x) {
modify(1, dfn[top[x]], dfn[x], d, t);
x = pa[top[x]];
}
return;
}
signed main() {
ios:: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int x, y; cin >> x >> y;
to[x].eb(y), to[y].eb(x);
}
buildtree(1, 0), decompose(1, 1), build(1, 1, n);
cin >> q;
while (q--) {
int op, x; cin >> op >> x;
if (!op) {
modifypath(x, co[x]);
co[x] = !co[x];
}
else {
if (a[1].min > n) { cout << -1 << "\n"; continue; }
int d = depth[x];
int res = 1e6;
while (x) {
res = min(res, d + query(1, dfn[top[x]], dfn[x]));
x = pa[top[x]];
}
cout << res << "\n";
}
}
return 0;
}
```