洛谷P2056 [ZJOI2007] 捉迷藏题解

题目链接：P2056 [ZJOI2007] 捉迷藏

题意：

cxy 和 q779 是一对好基友，并且他们有很多狗子。某天，cxy、q779 和狗子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 \(N\) 个屋子和 \(N-1\) 条双向走廊组成，这 \(N-1\) 条走廊的分布使得任意两个屋子都互相可达。

游戏是这样进行的，狗子们负责躲藏，cxy 负责找，而 q779 负责操纵这 \(N\) 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，狗子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，狗子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，cxy 希望知道可能的最远的两个狗子的距离（即最远的两个关灯房间的距离）。

我们将以如下形式定义每一种操作：

C i 改变第 \(i\) 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。

G 开始一次游戏，查询最远的两个关灯房间的距离。

输入格式：

第一行包含一个整数 \(N\)，表示房间的个数，房间将被编号为 \(1,2,3…N\) 的整数。

接下来 \(N-1\) 行每行两个整数 \(a,b\)，表示房间 \(a\) 与房间 \(b\) 之间有一条走廊相连。

接下来一行包含一个整数 \(Q\)，表示操作次数。接着 \(Q\) 行，每行一个操作，如上文所示。

输出格式：

对于每一个操作 G，输出一个非负整数，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出 0；若所有房间的灯都开着，输出 -1。

数据范围：

对于\(100\%\)的数据， \(1\le N \leq 10^5,~1\le Q \leq 5\times 10^5\)。

括号序列+线段树好题。（~~之前居然跟欧拉序搞混了，好傻啊我~~）

树的括号序列就是在 DFS 序外面加个括号。

括号序列构造方式如下：

从根开始 \(\mathtt{dfs}\) 。对于每个结点 \(u\) ，并加入一个 ( 和 \(u\) 。回溯时加入一个 ) 。

不难发现一棵 \(n\) 个结点的树的括号序列长度为 \(3n\) 。

例如下图的这棵树，它的括号序列为 (1(2(3)(4))(5(6)(7)))

对于树上两个结点 \(u,v\) ，如果我们把它的括号序列从 \(u\) 开始截取到 \(v\) ，

所得的子串去掉「匹配的括号及其包括的子串」后，剩余的括号数即为 \(u\) 到 \(v\) 的距离

例如上图中，截取括号序列 \(2\) 到 \(7\) 的部分为 2(3)(4))(5(6)(7

去掉「匹配的括号及其包括的子串」后，为 2)(5(7 ，剩余括号为 )(( ，因此 \(2\) 到 \(7\) 的距离为 \(3\) 。

接下来的问题就是如何维护

若干次的修改操作，其中关灯的房间为有效的结点。
使得去掉「匹配的括号及其包括的子串」后的剩余括号数最大的一对结点。

不难发现剩余的括号一定为 ))...)((...( 的形式，即若干个右括号拼上若干个左括号。

有没有觉得这东西有点像魔改过的区间最大子段和？

如果做过 SP1716 GSS3 ，会更容易理解下文的内容。

考虑线段树。我们要维护以下信息：

l 表示该区间内剩余的 ) 数，显然他们都在左边。
r 表示该区间内剩余的 ( 数，显然他们都在右边。
lc 表示该区间最长有效前缀的长度。例：段 ))1)))(2(3( 的 lc 值为 \(7\) ，因为以有效点 3 为结尾的前缀括号数为 \(7\) 。
rc 表示该区间最长有效后缀的长度。例：段 ))1)))(2(3( 的 rc 值为 \(6\) ，因为有效点 1 为开头的后缀的括号数为 \(6\) 。
ld 表示该区间有效前缀中「 ( 数 - ) 数」的最大值。例：段 ))1)))(2(3( 的 ld 值为 \(-2\) ，因为以有效点 1 结尾的前缀有 \(0\) 个 ( 和 \(2\) 个 ) 。
rd 表示该区间有效后缀中「 ) 数 - ( 数」的最大值。例：段 ))1)))(2(3( 的 rd 值为 \(0\) ，因为以有效点 1 为开头的后缀有 \(3\) 个 ) 和 \(3\) 个 ( 。
ans 表示该区间有效点对间的剩余括号数量的最大值。例：段 ))1)))(2(3( 的 ans 值为 \(5\) ，因为 1 到 3 之间有 \(5\) 个剩余括号。

~~要维护这么多东西，有点害怕（~~

叶子结点的初始值如下：

( （左括号）：l=0, r=1, lc=-INF, rc=-INF, ld=-INF, rd=-INF, ans=-INF 。

) （右括号）：l=1, r=0, lc=-INF, rc=-INF, ld=-INF, rd=-INF, ans=-INF 。

u （有效点）：l=0, r=0, lc=0, rc=0, ld=0, rd=0, ans=-INF 。

考虑线段树上的合并操作：

记左儿子为 \(a\) ，右儿子为 \(b\) 。

可以看这个来理解下面的合并 )))(((( | )))((((

l ：有两种情况：
- 第一种为 a.l 。
- 第二种为 a.l - a.r + b.l ，这里的减就是去掉匹配的括号。
因此 l = max(a.l, a.l - a.r + b.l) 。
r ：有两种情况：
- 第一种为 b.r 。
- 第二种为 b.r - b.l + a.r ，这里的减就是去掉匹配的括号。
因此 r = max(b.r, b.r - b.l + a.r) 。

lc ：有三种情况：
- 第一种为 a.lc 。
- 第二种为 a.l - a.r + b.lc ，表示 \(a\) 的 ( 与 \(b\) 的 ) 相抵消后还有多余的 ) 。
- 第三种为 a.l + a.r + b.ld ，表示 \(a\) 的 ( 与 \(b\) 的 ) 相抵消后还有多余的 ( 。
因此 lc = max({a.lc, a.l - a.r + b.lc, a.l + a.r + b.ld}) 。
rc ：有三种情况：
- 第一种 b.rc 。
- 第二种为 b.r - b.l + a.rc ，表示 \(b\) 的 ) 与 \(a\) 的 ( 相抵消后还有多余的 ( 。
- 第三种为 b.r + b.l + a.rd ，表示 \(b\) 的 ) 与 \(a\) 的 ( 相抵消后还有多余的 ) 。
因此 rc = max({b.rc, b.r - b.l + a.rc, b.r + b.l + a.rd}) 。

ld ：有两种情况：
- 第一种：a.ld 。
- 第二种：a.r - a.l + b.ld ，根据定义可知。
因此 ld = max(a.ld, b.ld + a.r - a.l) 。
rd ：有两种情况：
- 第一种： b.ld
- 第二种：b.l - b.r + a.rd ，根据定义可知。
因此 rd = max(b.rd, a.rd + b.l - b.r) 。

ans ：有三种情况：
- 第一种：max(a.ans, b.ans) 。
- 第二种：a.rc + b.ld ，表示 \(a\) 的 ( 多余。
- 第三种：a.rd + b.lc ，表示 \(b\) 的 ) 多余。

~~呼，总算写完这一大堆了。~~

最后的答案为根节点的 ans 。单点修改直接修就好了

时间复杂度 \(\mathcal{O}(n + Q\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

#define ls(at) (at << 1)
#define rs(at) (at << 1 | 1)

int n,Q,cnt,pos=1,head[N],val[N * 3],id[N];
struct Edge{ int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u]=pos; }

struct node
{
    int l,r,lc,rc,ld,rd,ans;
    node (int v = 0) : l(0), r(0), lc(-INF), rc(-INF), ld(-INF), rd(-INF), ans(-INF)
    {
        switch(v)
        {
            case -1: r = 1; break;
            case -2: l = 1; break;
            case 1: lc=rc=ld=rd=0; break;
        }
    }
}tr[N * 12]; // 4 * 3n
node merge(node a,node b)
{
    node c = 0;
    c.l = max(a.l, a.l - a.r + b.l);
    c.r = max(b.r, b.r - b.l + a.r);
    c.lc = max({a.lc, a.l - a.r + b.lc, a.l + a.r + b.ld});
    c.rc = max({b.rc, b.r - b.l + a.rc, b.r + b.l + a.rd});
    c.ld = max(a.ld, b.ld + a.r - a.l);
    c.rd = max(b.rd, a.rd + b.l - b.r);
    c.ans = max({a.ans, b.ans, a.rc + b.ld, a.rd + b.lc});
    return c;
}
void build(int l,int r,int at)
{
    if(l==r) return tr[at] = node(val[l]), void(0);
    int mid = (l+r-1) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    tr[at] = merge(tr[ls(at)], tr[rs(at)]);
}
void modify(int l,int r,int k,int at)
{
    if(l==r) return tr[at] = node(val[l]), void(0);
    int mid = (l+r-1) >> 1;
    if(k <= mid) modify(l,mid,k,ls(at));
    else modify(mid+1,r,k,rs(at));
    tr[at] = merge(tr[ls(at)], tr[rs(at)]);
}
void dfs(int u,int f)
{
    val[++cnt] = -1; val[++cnt] = 1; id[u] = cnt;
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v != f) dfs(e[i].v, u);
    val[++cnt] = -2;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    int tmp=n; dfs(1,0);
    build(1,cnt,1); char op; int v;
    for(cin >> Q; Q; Q--)
    {
        cin >> op;
        if(op == 'C')
        {
            cin >> v;
            (val[v = id[v]] ^= 1) ? ++tmp : --tmp; // val[v]=1 则未点亮
            modify(1,cnt,v,1);
        }else
        {
            if(tmp <= 1) cout << tmp-1 << '\n'; // tmp 为未点亮的灯的个数
            else cout << tr[1].ans << '\n';
        }
    }
    return 0;
}