BZOJ1095: [ZJOI2007]Hide 捉迷藏【动态点分治】

Description

　　捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩

捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋

子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的

时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要

求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两

个孩子的距离（即最远的两个关灯房间的距离）。我们将以如下形式定义每一种操作： C(hange) i 改变第i个房

间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的

距离。

Input

　　第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，

表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如

上文所示。

Output

　　对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关

着灯的，输出0；若所有房间的灯都开着，输出-1。

Sample Input

8

1 2

2 3

3 4

3 5

3 6

6 7

6 8

7

G

C 1

G

C 2

G

C 1

G

Sample Output

4

3

3

4

HINT

对于100%的数据， N ≤100000, M ≤500000。

思路

先讲一讲动态点分治做法

剩下的好像还有一个线段树维护括号序列明天填坑

树上路径问题，链剖行不通啊咋办

就想用点分治做，考虑经过每一个点的贡献

那么就先把点分树建出来，尝试进行维护发现是我们对于一个点分树上的节点，考虑所有他的字节点，分别管理了这个节点的所有的子树，我们要知道到每一个子树中黑色节点到这个点的距离并取出最大和次大

维护三个堆\(own,subtree,total\)

为了维护这个东西（最大和次大），我们先用\(own\)维护出每个节点所有管辖黑色节点到这个节点的点分树父亲节点的距离

然后我们记录\(subtree\)为每一个点分树上的节点的所有子树的节点到这个节点的最大值

那么为了方便更新答案，再用\(total\)记录每一个节点的\(subtree\)中最大和次大的和

注意每次修改一个节点的颜色的时候，它本身对自己的subtree堆是有一个0的长度的，如果不添加那你对于这个节点就默认他没有改变，就错了

其次是写的时候注意运算逻辑的先后顺序，不然会很可怕的

堆的维护。。。我是用两个堆实现的支持\(push,pop,top,max+secondmax\)的数据结构

#include<bits/stdc++.h>

using namespace std;

int read() {

  int res = 0, w = 1; char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = -1, c = getchar();

  while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();

  return res * w;

}

const int N = 1e5 + 10;

const int LOG = 20;

struct Heap {

  priority_queue<int> a, b;

  void push(int vl) {

    a.push(vl);

  }

  void pop(int vl) {

    b.push(vl);

  }

  int size() {

    return a.size() - b.size();

  }

  int top() {

    while (b.size() && a.top() == b.top()) {

      a.pop();

      b.pop();

    }

    if (a.size()) return a.top();

    else return 0;

  }

  int calc() { //max + second_max

    if (size() < 2) return 0;

    int tp = top();

    pop(tp);

    int res = top() + tp;

    push(tp);

    return res;

  }

};

struct Edge {

  int v, nxt;

  Edge(int v = 0, int nxt = 0): v(v), nxt(nxt) {}

} E[N << 1];

int head[N], tot = 0;

int n, q, num = 0, col[N] = {0};

char c[10];

void addedge(int u, int v) {

  E[++tot] = Edge(v, head[u]);

  head[u] = tot;

}

namespace LCA {

struct Node {

  int id, depth;

  Node(int id = 0, int depth = 0): id(id), depth(depth) {}

  bool operator < (const Node b) const {

    return depth < b.depth;

  }

} ST[N << 1][LOG];

int first[N], dep[N], log[N << 1], len;

void dfs(int u, int fa) {

  dep[u] = dep[fa] + 1;

  ST[++len][0] = Node(u, dep[u]);

  first[u] = len;

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (v == fa) continue;

    dfs(v, u);

    ST[++len][0] = Node(u, dep[u]);

  }

}

void init() {

  dfs(1, 0);

  log[1] = 0;

  for (int i = 2; i <= len; i++) log[i] = log[i >> 1] + 1;

  for (int j = 1; (1 << j) <= len; j++) {

    for (int i = 1; i + (1 << j) - 1 <= len; i++) {

      ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);

    }

  }

}

int getdis(int u, int v) {

  if (first[u] < first[v]) swap(u, v);

  int k = log[first[u] - first[v] + 1];

  int lca = min(ST[first[v]][k], ST[first[u] - (1 << k) + 1][k]).id;

  return dep[u] + dep[v] - (dep[lca] << 1);

}

}

namespace Tree_Devide {

Heap total, subtree[N], own[N];

int father[N];

int siz[N], F[N], siz_all, rt;

bool vis[N]; 

void getsiz(int u, int fa) {

  siz[u] = 1;

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (v == fa || vis[v]) continue;

    getsiz(v, u);

    siz[u] += siz[v];

  }

}

void getroot(int u, int fa) {

  F[u] = 0;

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (v == fa || vis[v]) continue;

    getroot(v, u);

    F[u] = max(F[u], siz[v]);

  }

  F[u] = max(F[u], siz_all - siz[u]);

  if (F[u] < F[rt]) rt = u;

}

void solve(int u, int fa) {

  father[u] = fa;

  vis[u] = 1;

  getsiz(u, 0);

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (vis[v]) continue;

    F[rt = 0] = siz_all = siz[v];

    getroot(v, 0);

    solve(rt, u);

  }

}

void init() {

  getsiz(1, 0);

  F[rt = 0] = siz_all = n;

  getroot(1, 0);

  solve(rt, 0);

}

void turn_off(int u) {

  subtree[u].push(0);

  if (subtree[u].size() == 2) total.push(subtree[u].calc());

  for (int cur = u; father[cur]; cur = father[cur]) {

    int dis = LCA::getdis(u, father[cur]);

    int lasttop = own[cur].top();

    own[cur].push(dis);

    if (dis <= lasttop) continue;

    int lastmax = subtree[father[cur]].calc(), lastsiz = subtree[father[cur]].size();

    if (lasttop) subtree[father[cur]].pop(lasttop);

    subtree[father[cur]].push(dis);

    int nowmax = subtree[father[cur]].calc(), nowsiz = subtree[father[cur]].size();

    if (nowmax > lastmax) {

      if (lastsiz >= 2) total.pop(lastmax);

      if (nowsiz >= 2) total.push(nowmax);

    }

  }

}

void turn_on(int u) {

  if (subtree[u].size() == 2) total.pop(subtree[u].calc());

  subtree[u].pop(0);

  for (int cur = u; father[cur]; cur = father[cur]) {

    int dis = LCA::getdis(u, father[cur]);

    int lasttop = own[cur].top();

    own[cur].pop(dis);

    if (dis != lasttop) continue;

    int lastmax = subtree[father[cur]].calc(), lastsiz = subtree[father[cur]].size();

    subtree[father[cur]].pop(dis);

    if (own[cur].top()) subtree[father[cur]].push(own[cur].top());

    int nowmax = subtree[father[cur]].calc(), nowsiz = subtree[father[cur]].size();

    if (nowmax < lastmax) {

      if (lastsiz >= 2)total.pop(lastmax);

      if (nowsiz >= 2) total.push(nowmax);

    }

  }

}

}

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  n = read();

  for (int i = 1; i < n; i++) {

    int u = read(), v = read();

    addedge(u, v);

    addedge(v, u);

  }

  LCA::init();

  Tree_Devide::init();

  for (int i = 1; i <= n; i++) Tree_Devide::own[i].push(0);

  for (int i = 1; i <= n; i++) {

    ++num;

    Tree_Devide::turn_off(i);

  }

  q = read();

  while (q--) {

    scanf("%s", c);

    if (c[0] == 'C') {

      int u = read();

      if (col[u]) Tree_Devide::turn_off(u), tot++;

      else Tree_Devide::turn_on(u), tot--;

      col[u] ^= 1;

    } else {

      if (num == 0) printf("-1\n");

      else if (num == 1) printf("0\n");

      else printf("%d\n", Tree_Devide::total.top());

    }

  }

  return 0;

}

巴特西