Bzoj 1095 [ZJOI2007]Hide hide and seek dynamic point division + heap / line segment tree

题面

题传送门

解法

数据结构题......

  • 说两两A different way of thinking, how to do with the brackets sequence I will not
  • because there are modifications and there are questions about the distance between the points, so we consider the dynamic point division
  • first build a point tree, then Open two heaps at each point. "The first heap records the distance from all nodes in the subtree to the parent node, and the second heap records the top of all the subnodes. Then the largest and the second largest in the heap 2 of a node are added to the subtree. The longest chain. Then we finally open a global heap, record the sum of the maximum and the second largest of all heaps 2. Then the global heap top is the answer." -PoPoQQQ ( Because I am lazy, I don't plan to play it myself)
  • 时间复杂:O(qlog2n)O(qlog2n)
  • Consider another way, we can build a line segment tree for the whole tree dfsdfs Each point maintains the dfsdfs two endpoints of the diameter in the point corresponding to the sequence interval
  • Obviously, this information can be merged, each modification is a single point to modify a value
  • 时间Complexity: O(qlogn)O(qlogn)(rmq seeking lcalca) or O(qlog2n)O(qlog2n)
  • These two methods can pass this question

because of dynamic point division + The heap is more troublesome, so I still put the code of the line segment tree.

#include <bits/stdc++.h>
#define N 100010
using namespace std;
template <typename node> void chkmax(node &x, node y) {x = max(x, y);}
template <typename node> void chkmin(node &x, node y) {x = min(x, y);}
template <typename node> void read(node &x) {
    x = 0; int f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
struct Edge {
    int next, num;
} e[N * 3];
struct Node {
    int x, y;
} t[N * 4];
int cnt, Time, d[N], col[N], dfn[N], rea[N], f[N][17];
void add(int x, int y) {
    e[++cnt] = (Edge) {e[x].next, y};
    e[x].next = cnt;
}
void dfs(int x, int fa) {
    d[x] = d[fa] + 1, dfn[x] = ++Time, rea[Time] = x;
    for (int i = 1; i <= 16; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int p = e[x].next; p; p = e[p].next) {
        int k = e[p].num;
        if (k == fa) continue; f[k][0] = x;
        dfs(k, x);
    }
}
int dis(int x, int y) {
    if (!x) swap(x, y);
    if (x == 0 || y == 0) return (x == 0) ? -1 : 0;
    int tx = x, ty = y;
    if (d[x] < d[y]) swap(x, y);
    for (int i = 16; ~i; i--)
        if (d[f[x][i]] >= d[y]) x = f[x][i];
    if (x == y) return d[tx] + d[ty] - 2 * d[x];
    for (int i = 16; ~i; i--)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    x = f[x][0]; return d[tx] + d[ty] - 2 * d[x];
}
void update(int k) {
    int lc = k << 1, rc = k << 1 | 1, ansx = 0, ansy = 0;
    int mx = -INT_MAX, tmp[5] = {0, t[lc].x, t[lc].y, t[rc].x, t[rc].y};
    for (int i = 1; i < 4; i++)
        for (int j = i + 1; j <= 4; j++) {
            int x = tmp[i], y = tmp[j], z = dis(x, y);
            if (z > mx) mx = z, ansx = x, ansy = y;
        }
    t[k] = (Node) {ansx, ansy};
}
void build(int k, int l, int r) {
    if (l == r) {t[k].x = rea[l], col[rea[l]] = 1; return;}
    int mid = (l + r) >> 1;
    build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
    update(k);
}
void modify(int k, int l, int r, int x) {
    if (l == r) {col[rea[x]] ^= 1, t[k].x = (col[rea[x]] == 1) ? rea[x] : 0; return;}
    int mid = (l + r) >> 1;
    if (x <= mid) modify(k << 1, l, mid, x);
        else modify(k << 1 | 1, mid + 1, r, x);
    update(k);
}
int main() {
    int n; read(n); cnt = n;
    for (int i = 1; i < n; i++) {
        int x, y; read(x), read(y);
        add(x, y), add(y, x);
    }
    dfs(1, 0);
    build(1, 1, n);
    int q, tot = n; read(q);
    while (q--) {
        char c = getchar();
        while (!isalpha(c)) c = getchar();
        if (c == 'G') {
            if (tot < 2) {cout << tot - 1 << "\n"; continue;}
            cout << dis(t[1].x, t[1].y) << "\n"; continue;
        }
        int x; read(x);
        if (col[x]) tot--; else tot++;
        modify(1, 1, n, dfn[x]);
    }
    return 0;
}