题意概述
有一棵$N$个节点的树,每个节点都是黑色或白色。有$Q$次操作,动态修改点的颜色,询问最远黑点对之间的距离。
数据范围:$1 \le N \le 10^5, \; 1 \le Q \le 5 \times 10^5$。
算法分析
考虑点分治,构造一棵重心树。为了方便,下面所有距离均表示在原树上的距离,堆均为大根堆。
设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆,第一个堆用来维护重心树上$u$子树中的所有黑点到$p_u$的距离,第二个堆用来维护重心树上$u$各个子树中距离$u$最远的黑点到$u$的距离。那么第二个堆可以借助第一个堆来维护。
接着需要一个全局的堆,用来维护所有节点第二个堆的前两个元素之和(经过该点的路径)以及所有黑点第二个堆的第一个元素(以该点为端点的路径)。
修改时,沿着重心树往上依次处理经过的节点,先在全局的堆中删除,再在第二个堆中删除,在第一个堆中修改后,维护第二个堆和全局的堆。
代码
/* * Computer programmers do it byte by byte. */ #include <algorithm> #include <cstdio> #include <cstring> #include <queue> template <typename T> void read(T &n) { char c; for (; (c = getchar()) < '0' || c > '9';) ; for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0') ; } typedef int const ic; static ic N = 100005; class heap { private: std::priority_queue<int> que, buf; void clear() { for (; !que.empty() && !buf.empty() && que.top() == buf.top(); que.pop(), buf.pop()) ; } public: void push(ic &n) { if (n) que.push(n); } void erase(ic &n) { if (n) buf.push(n); } void pop() { clear(); if (!que.empty()) que.pop(); } int top() { clear(); return que.empty() ? 0 : que.top(); } int top2() { clear(); if (que.empty()) return 0; int tmp = que.top(), ret = tmp; que.pop(), clear(); if (que.empty()) { que.push(tmp); return 0; } ret += que.top(), que.push(tmp); return ret; } } global; namespace tree { int n, nume, h[N], col[N]; int tim, fi[N], dep[N], lca[N << 1][20]; int power[N << 1]; int root, up[N], size[N], mx[N], vis[N]; heap toup[N], me[N]; struct Edge { int v, nxt; } e[N << 1]; void add_edge(ic &u, ic &v) { e[++nume] = (Edge){v, h[u]}, h[u] = nume; e[++nume] = (Edge){u, h[v]}, h[v] = nume; } void dfs(ic &t, ic &fa) { lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) dfs(e[i].v, t), lca[++tim][0] = t; } void init() { for (int i = 2; i <= tim; i <<= 1) ++power[i]; for (int i = 1; i <= tim; ++i) power[i] += power[i - 1]; for (int i = 1; i < 20; ++i) for (int j = 1; j <= tim; ++j) { ic k = std::min(tim, j + (1 << i - 1)); lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1] : lca[k][i - 1]; } } int get_lca(ic &u, ic &v) { ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]); ic len = power[r - l + 1], k = r - (1 << len) + 1; return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len]; } int get_dist(ic &u, ic &v) { ic lca = get_lca(u, v); return dep[u] + dep[v] - 2 * dep[lca]; } int get_size(ic &t, ic &fa) { int ret = 1; for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v] && e[i].v != fa) ret += get_size(e[i].v, t); return ret; } void get_root(ic &t, ic &fa, ic &tot) { size[t] = 1, mx[t] = 0; for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v] && e[i].v != fa) get_root(e[i].v, t, tot), size[t] += size[e[i].v], mx[t] = std::max(mx[t], size[e[i].v]); (mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t); } void init_heap(ic &t, ic &fa, ic &dep, heap &hp) { hp.push(dep); for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v] && e[i].v != fa) init_heap(e[i].v, t, dep + 1, hp); } void build(int t) { vis[t] = true; for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v]) root = 0, get_root(e[i].v, 0, size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)), up[root] = t, init_heap(e[i].v, t, 1, toup[root]), me[t].push(toup[root].top()), build(root); global.push(me[t].top()), global.push(me[t].top2()); } void modify(int t) { ic p = t; if (col[t]) global.erase(me[t].top()); else global.push(me[t].top()); for (; up[t]; t = up[t]) { if (col[up[t]]) global.erase(me[up[t]].top()); global.erase(me[up[t]].top2()); me[up[t]].erase(toup[t].top()); if (col[p]) toup[t].erase(get_dist(p, up[t])); else toup[t].push(get_dist(p, up[t])); me[up[t]].push(toup[t].top()); if (col[up[t]]) global.push(me[up[t]].top()); global.push(me[up[t]].top2()); } col[p] = !col[p]; } } // namespace tree int main() { read(tree::n), tree::mx[0] = tree::n; for (int i = 1, u, v; i < tree::n; ++i) read(u), read(v), tree::add_edge(u, v); tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n), tree::build(tree::root); for (int i = 1; i <= tree::n; ++i) tree::col[i] = 1; int q; for (read(q); q--;) { char c; scanf(" %c", &c); if (c == 'G') printf("%d\n", global.top()); else { int p; read(p), tree::modify(p); } } return 0; }