[BZOJ1095][ZJOI2007]Hide 捉迷藏

给定一个n个点的树,每个点有黑白两种颜色。进行m次操作:改变一个点的颜色,或查询最远的两个白点的距离。

链接

BZOJ 1095

题解

两个点间的距离可以用这两个点的深度之和减去两倍的LCA的深度来求:

dis(a, b)\\  = dep(a) + dep(b) - 2dep(LCA(a, b))\\  = (dep(a) - dep(LCA(a, b)) + (dep(b) - dep(LCA(a, b)))

并且两个点的LCA就是括号序列中这两个点之间深度最小的点。

我们求出树的括号序列:左括号代表远离根走了一条边,权值为1;右括号代表靠近根走了一条边,权值为-1;还要给每个点分配一个权值为0的位置。

按照括号序列的顺序在两个点之间遍历,每遇到一个左括号,当前深度就会+1;每遇到一个右括号,当前深度就会-1dep(a) - dep(LCA(a, b))就是在括号序列上从a走到LCA(a, b)途中右括号的数量减左括号的数量,dep(b) - dep(LCA(a, b))就是在括号序列上从LCA(a, b)走到$b$途中左括号的数量减去右括号的数量。从aLCA(a, b)在括号序列上对应着从$a$到$b$的一个前缀,因此,两个点间的距离就是括号序列上以这两个点为端点的子串,翻转一个前缀后的最大权值和。

现在,问题转化成了:改变序列上一个点的颜色,求以两个白点为端点的子段,翻转一个前缀的权值后最大的和是多少。这个问题可以用类似Vijos1083 小白逛公园的方法用线段树维护。

代码
#include <bits/stdc++.h>

using namespace std;

const int SizN = 1e5 + 10, Inf = 1e9;

struct Node {
    Node *L, *R;
    int l, r, m, ___, l__, _m_, __r, lm_, _mr, lmr;
    Node(int l, int r);
    void push_up();
    void flip(int x);
} *root;

int N, fa[SizN], id[SizN], seq[SizN * 3], ns;
bool enable[SizN * 3];
vector<int> edge[SizN];

Node::Node(int l, int r) : l(l), r(r), m((l + r) / 2) {
    if(l != r) {
        L = new Node(l, m);
        R = new Node(m + 1, r);
    }
    push_up();
}

void Node::push_up() {
    if(l == r) {
        ___ = seq[l]; _m_ = abs(seq[l]);
        l__ = __r = lm_ = _mr = lmr = enable[l] ? 0 : -Inf;
    } else {
        ___ = L->___ + R->___;
        _m_ = max(L->_m_ + R->___,  R->_m_ - L->___);
        l__ = max(R->l__, L->l__ - R->___);
        __r = max(L->__r, L->___ + R->__r);
        lm_ = max(R->lm_, max(L->lm_ + R->___, L->l__ + R->_m_));
        _mr = max(L->_mr, max(R->_mr - L->___, R->__r + L->_m_));
        lmr = max(max(L->lmr, R->lmr), max(L->lm_ + R->__r, L->l__ + R->_mr));
    }
}

void Node::flip(int x) {
    if(l != r) {
        if(x <= m) L->flip(x);
        else R->flip(x);
    } else enable[x] ^= true;
    push_up();
}

void dfs(int x) {
    seq[++ns] = 1;
    seq[id[x] = ++ns] = 0;
    for(vector<int>::iterator i = edge[x].begin(); i != edge[x].end(); i++) {
        if(*i == fa[x]) continue;
        fa[*i] = x; dfs(*i);
    }
    seq[++ns] = -1;
}

int main() {
    scanf("%d", &N);
    for(int i = 1; i < N; i++) {
        int a, b; scanf("%d%d", &a, &b);
        edge[a].push_back(b); edge[b].push_back(a);
    }
    dfs(1);
    for(int i = 1; i <= N; i++) enable[id[i]] = true;
    root = new Node(1, ns);
    int Q; scanf("%d", &Q);
    for(int i = 1; i <= Q; i++) {
        char op[5]; scanf("%s", op + 1);
        if(op[1] == 'C') {
            int x; scanf("%d", &x);
            root->flip(id[x]);
        } else {
            printf("%d\n", root->lmr < 0 ? -1 : root->lmr);
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注