题解：P13065 [GCJ 2020 #2] Emacs++

reinforest · 2025-08-28 20:13:12 · 题解

你说的对，但是 abv3Rpkg 说得太抽象了。

前置知识：树上 dp，倍增，矩阵运算，代码能力。

看到“最短时间”的东西，就可以看出来这是一道最短路径的题目了，重点是建图和对图结构的观察。

Part 1：建图

实际上很简单，对于两个相邻的点 (i,i+1)，从 i \rightarrow i+1 连边权为 R_i 的边，从 i+1 \rightarrow i 连边权为 L_i 的边；并且对于匹配的括号对 (i,j)，从 i \rightarrow j 连边权为 P_i 的边，从 j \leftarrow i 连边权为 P_j 的边。比如说，对于字符串 ()(()())(())，图的结构是这样的：（为了方便，我们在字符串的最外面补上一层括号使它们连通）

我们可以发现一些性质：

1. 如果把匹配上的两个点（比如 (1,2),(10,11) 等）缩成一个点，那么整张图就是一个仙人掌，并且每个点都在至多两个点双连通分量中。

点双连通分量指不存在割点的子图，删除任意单个非端点节点仍保持连通；
仙人掌是指每条边至多在一个点双连通分量的图。

2. 如果我们从 dfs 的角度理解括号匹配，比如遇到一个 ( 就递归，遇到 ) 就回溯，可以形成一个树形结构，整颗树是这样的：（其中蓝色圆圈代表节点，蓝色连边代表树上的边）

这棵树能够很好地表现这个图的一些性质。比如说，我们拿出来这棵树上的一个“父亲-所有儿子”的结构，这棵树上的这个结构在原图上的代表了一个环，同时，这个环在把匹配上的两个点缩起来之后，它就是一个点双。我们可以把这个“环”挂到父亲节点上。

实际上，在代码中建图也是依赖 dfs 的。其中 ring[u] 表示挂到 u 的环，G 表示这棵树，X[] 和 Y[] 数组分别表示树上的点所代表的左括号和由括号的下标，bl[] 数组表示字符串下标分别在树上的节点。

在以下的所有代码中，都有 #define ll long long。以下是建图的代码。

void pushring(ll u,ll v){
    ring[u].push_back(v);
}
void build_tree(){
    ll now=++tot;
    X[now]=cur;bl[cur]=now;
    pushring(now,cur);
    cur++;
    while(ch[cur]=='('){
        //遇到左括号就递归，遇到右括号就回溯
        pushring(now,cur);
        G[now].push_back(tot+1);
        G[tot+1].push_back(now);
        build_tree();
        pushring(now,cur);
        cur++;
    }
    Y[now]=cur;bl[cur]=now;
    pushring(now,cur);
}

Part 2：重标边权

我们知道，把图上每两个匹配的点缩成一个点，最后就是一个仙人掌。现在假定我们会了仙人掌最短路，先考虑“把每两个匹配的点缩成一个点”这个操作执行，会对答案产生哪些问题。

如图所示，我们想求 2 \rightarrow 9 的最短路，如果 3 \rightarrow 8 的边权过大，那么路径就可能绕过 3 \rightarrow 8 从而走到其它地方绕一圈，导致在同一个环上两个点的最短路不全在环上，这样不好控制以及计算了。

可以发现，出现问题的矛盾点是匹配上的点对。我们可以求出对于所有匹配上的点对，求出两两之间真正的最短路，然后重标边权，把新算出来的值作为新的 P_i。

可以发现，经过以上操作之后，同一个环上两个点的最短路就一定在环上了。

但是这个怎么求呢？还记得以上的树形结构吗？这里可以考虑树形 dp。这里设 x_u 表示树上 u 代表的左括号下标，y_u 表示 u 代表的右括号下标，S_u 表示 u 的所有孩子节点的集合。

可以发现，x_u，y_u 之间的最短路要么全在 u 子树内，要么全在 u 子树外，因而可设状态：