【算法】树形结构的化简

括号序

Introduce

对任意一个树结构,都有唯一对应的的一个括号编码
定义一个 [] 代表一个节点,其子节点被包含在括号中,我们在每个节点处加入其编号,放到括号内最前面,即 [1]

如一个由三个节点组成的满二叉树的括号编码为 [1[2][3]]

那么对于任意的两个节点,可以发现,假设取出其编号间的括号序列(忽略数字),再将匹配的括号去掉后, [] 的个数和即为两点间距离

如 $1-3$ 所对应的括号序列为 [][ ,去匹配括号后为 [ ,则两点距离为 1
如 $2-3$ 所对应的括号序列为 ][ ,去匹配括号后为 ][ ,则两点距离为 2

可以发现,对于去匹配的任意一个括号序列,其必然形似于 ]]][[[[

对左侧节点来说,每遇到一个 ] 相当于向父亲处走一步
对右侧节点来说,每遇到一个 [ 相当于向父亲处走一步

最后会在 LCA 处相遇

所以说 [ ] 个数和即为两者距离

Problem

对于 [ZJOI2017]捉迷藏 这道题可以使用动态点分治进行处理
同样的,也能够使用这里所提到的括号序列解决

题目需要动态维护两个黑点之间的最远距离,转化为了一个括号序列之后就变为了维护两个黑点之间处理后串的最大长度,也就是 ]]][[[[ 有多长

对于任意一段序列 $S$ ,可以将其用 [] 的个数进行表示,即 $S_i=(a_i,b_i)$ 其中 $a_i,b_i$ 分别表示 ][ 的个数, $|S_i|=a_i+b_i$

对于两段相邻序列 $S_1,S_2$ 进行合并,则中间的一部分 [] 会形成匹配后消去
若 $b_1<a_2$ ,则 $S=(a_1+a_2-b_1,b_2)$
若 $b_1>a_2$ ,则 $S=(a_1,b_1+b_2-a_2)$

那么,要维护两黑点之间 $|S|$ 的最大值,就需要维护如下几个量: $l(a+b),l(b-a),r(a+b),r(a-b)$

合并时的规则请自行推导

Code

#include <bits/stdc++.h>
using namespace std;

int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int MAX = 100000010;

int que[N * 3], top;
int pos[N];

#define L (ch[x][0])
#define R (ch[x][1])
#define mid ((l + r) >> 1)

struct Tree {
    int ch[N * 6][2], cnt = 1;
    int lplus[N * 6], lminus[N * 6];
    int rplus[N * 6], rminus[N * 6];
    int a[N * 6], b[N * 6]; // a -> ], b -> [
    int dis[N * 6];
    void update(int x) {
        a[x] = a[L] + max(a[R] - b[L], 0);
        b[x] = b[R] + max(b[L] - a[R], 0);
        dis[x] = max(dis[L], dis[R]);
        rplus[x] = max(rplus[L] - a[R] + b[R], rminus[L] + a[R] + b[R]);
        rplus[x] = max(rplus[x], rplus[R]);
        rminus[x] = max(rminus[L] + a[R] - b[R], rminus[R]);
        lplus[x] = max(lplus[R] + a[L] - b[L], lminus[R] + a[L] + b[L]);
        lplus[x] = max(lplus[x], lplus[L]);
        lminus[x] = max(lminus[R] - a[L] + b[L], lminus[L]);
        dis[x] = max(dis[x], rplus[L] + lminus[R]);
        dis[x] = max(dis[x], rminus[L] + lplus[R]);
    }
    void build(int x, int l, int r) {
        if(l == r) {
            if(que[l]) {
                lplus[x] = lminus[x] = rplus[x] = rminus[x] = - MAX;
                a[x] = (que[l] == - 1); b[x] = (que[l] == 1);
                dis[x] = - MAX;
            }
            else {
                lplus[x] = lminus[x] = rplus[x] = rminus[x] = 0;
                a[x] = b[x] = 0;
                dis[x] = - MAX;
            }
        }
        else {
            if(!L) L = ++ cnt;
            build(L, l, mid);
            if(!R) R = ++ cnt;
            build(R, mid + 1, r);
            update(x);
        }
    }
    void change(int x, int l, int r, int pos) {
        if(l == r) {
            if(!a[x] && !b[x])
                lplus[x] = lminus[x] = rplus[x] = rminus[x] = a[x] = b[x] = - MAX;
            else
                lplus[x] = lminus[x] = rplus[x] = rminus[x] = a[x] = b[x] = 0;
        }
        else {
            if(pos <= mid)
                change(L, l, mid, pos);
            else
                change(R, mid + 1, r, pos);
            update(x);
        }
    }
}tr;

int n, q;
struct Edge {
    int t, n;
}e[N << 1];
int head[N], Etot;

char opt[10];

void addedge(int a, int b) {
    e[++ Etot] = {b, head[a]};
    head[a] = Etot;
    e[++ Etot] = {a, head[b]};
    head[b] = Etot;
}

void dfs(int x, int fa) {
    que[++ top] = 1;
    que[++ top] = 0;
    pos[x] = top;
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == fa) continue;
        dfs(e[i].t, x);
    }
    que[++ top] = - 1;
}

int main() {
    n = read();
    for(int i = 1; i < n; ++ i)
        addedge(read(), read());
    dfs(1, 0);
    tr.build(1, 1, 3 * n);
    q = read();
    while(q --) {
        scanf("%s", opt);
        if(opt[0] == 'G')
            printf("%d\n", tr.dis[1] > 0 ? tr.dis[1] : - 1);
        else
            tr.change(1, 1, 3 * n, pos[read()]);
    }
    return 0;
}

Codeforces 1149C Tree Generator™

DFS序和逆DFS序

肯定不会咕的!(确信

Comments

添加新评论