Hide

题意概述

有一棵$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;
}