专栏文章

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

rreinforest
P13065题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mio3250j
此快照首次捕获于
2025/12/02 12:33
3 个月前
此快照最后确认于
2025/12/02 12:33
3 个月前
查看原文
你说的对，但是 abv3Rpkg 说得太抽象了。
前置知识：树上 dp，倍增，矩阵运算，代码能力。
看到“最短时间”的东西，就可以看出来这是一道最短路径的题目了，重点是建图和对图结构的观察。

Part 1：建图

实际上很简单，对于两个相邻的点 (i,i+1)(i,i+1)，从 i→i+1i \rightarrow i+1 连边权为 RiR_i 的边，从 i+1→ii+1 \rightarrow i 连边权为 LiL_i 的边；并且对于匹配的括号对 (i,j)(i,j)，从 i→ji \rightarrow j 连边权为 PiP_i 的边，从 j←ij \leftarrow i 连边权为 PjP_j 的边。比如说，对于字符串 ()(()())(())，图的结构是这样的：（为了方便，我们在字符串的最外面补上一层括号使它们连通）
我们可以发现一些性质：
  1. 如果把匹配上的两个点（比如 (1,2),(10,11)(1,2),(10,11) 等）缩成一个点，那么整张图就是一个仙人掌，并且每个点都在至多两个点双连通分量中。
点双连通分量指不存在割点的子图，删除任意单个非端点节点仍保持连通；
仙人掌是指每条边至多在一个点双连通分量的图。
  1. 如果我们从 dfs 的角度理解括号匹配，比如遇到一个 ( 就递归，遇到 ) 就回溯，可以形成一个树形结构，整颗树是这样的：（其中蓝色圆圈代表节点，蓝色连边代表树上的边）
这棵树能够很好地表现这个图的一些性质。比如说，我们拿出来这棵树上的一个“父亲-所有儿子”的结构，这棵树上的这个结构在原图上的代表了一个环，同时，这个环在把匹配上的两个点缩起来之后，它就是一个点双。我们可以把这个“环”挂到父亲节点上。
实际上，在代码中建图也是依赖 dfs 的。其中 ring[u] 表示挂到 uu 的环，G 表示这棵树，X[] 和 Y[] 数组分别表示树上的点所代表的左括号和由括号的下标，bl[] 数组表示字符串下标分别在树上的节点。
在以下的所有代码中，都有 #define ll long long。以下是建图的代码。
CPP
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→92 \rightarrow 9 的最短路，如果 3→83 \rightarrow 8 的边权过大，那么路径就可能绕过 3→83 \rightarrow 8 从而走到其它地方绕一圈，导致在同一个环上两个点的最短路不全在环上，这样不好控制以及计算了。
可以发现，出现问题的矛盾点是匹配上的点对。我们可以求出对于所有匹配上的点对，求出两两之间真正的最短路，然后重标边权，把新算出来的值作为新的 PiP_i。
可以发现，经过以上操作之后，同一个环上两个点的最短路就一定在环上了。
但是这个怎么求呢？还记得以上的树形结构吗？这里可以考虑树形 dp。这里设 xux_u 表示树上 uu 代表的左括号下标，yuy_u 表示 uu 代表的右括号下标，SuS_u 表示 uu 的所有孩子节点的集合。
可以发现，xux_u，yuy_u 之间的最短路要么全在 uu 子树内，要么全在 uu 子树外，因而可设状态：
fu,0f_{u,0} 表示 uu 子树内，从 xux_u 走到 yuy_u 的最短路。
fu,1f_{u,1} 表示 uu 子树内，从 yuy_u 走到 xux_u 的最短路。
gu,0g_{u,0} 表示 uu 子树外，从 xux_u 走到 yuy_u 的最短路。
gu,1g_{u,1} 表示 uu 子树外，从 yuy_u 走到 xux_u 的最短路。
接下来就是转移。设 vv 是 uu 的一个孩子，我们可以考虑先转移前两个状态，可以从下往上转移。
fu,0=min⁡{Pxu,Rxu+∑v∈Su(Ryv+fv,0)}f_{u,0}=\min\{P_{x_u},R_{x_u}+\sum_{v \in S_{u} } (R_{y_v}+f_{v,0})\}
fu,1=min⁡{Pyu,Lyu+∑v∈Su(Lxv+fv,1)}f_{u,1}=\min\{P_{y_u},L_{y_u}+\sum_{v \in S_{u} } (L_{x_v}+f_{v,1})\}
这条路径一定是从父亲的一个点出发，然后往下走到儿子节点，绕一圈再走回来。
我们写出 gg 的转移式子，稍微复杂一点。因为这条路径是子树外的，我们考虑从上往下转移。
gv,0=min⁡{Pxv,gu,0+Lyu+∑v′∈SuLxv′+∑v′∈Su∧v′≠vfv′,1}g_{v,0}=\min\{P_{x_v},g_{u,0} + L_{y_u}+\sum_{v' \in S_u}L_{x_{v'}} + \sum_{v' \in S_{u} ∧ v' \not= v}f_{v',1} \}
gv,1=min⁡{Pyv,gu,1+Rxu+∑v′∈SuRxv′+∑v′∈Su∧v′≠vfv′,0}g_{v,1}=\min\{P_{y_v},g_{u,1} + R_{x_u}+\sum_{v' \in S_u}R_{x_{v'}} + \sum_{v' \in S_{u} ∧ v' \not= v}f_{v',0} \}
这条路径一定是从儿子的一个点出发，往上绕到父亲节点，绕一圈再走回来。
转移结束，对于所有的 uu，让 Pxu←min⁡(fu,0,gu,0),Pyu←min⁡(fu,1,gu,1)P_{x_u} \leftarrow \min(f_{u,0},g_{u,0}),P_{y_u} \leftarrow \min(f_{u,1},g_{u,1})。
以下就是转移的代码。
CPP
void get_f(ll u,ll fat){
    ll sum[2]={R[X[u]],L[Y[u]]};
    for(auto v:G[u]){
        if(v==fat)continue;
        get_f(v,u);
        sum[0]+=R[Y[v]]+f[v][0];
        sum[1]+=L[X[v]]+f[v][1];
    }
    f[u][0]=min(sum[0],P[X[u]]);
    f[u][1]=min(sum[1],P[Y[u]]);
}
void get_g(ll u,ll fat){
    ll sum[2]={L[Y[u]]+g[u][0],R[X[u]]+g[u][1]};
    for(auto v:G[u]){
        if(v==fat)continue;
        sum[0]+=L[X[v]]+f[v][1];
        sum[1]+=R[Y[v]]+f[v][0];
    }
    for(auto v:G[u]){
        if(v==fat)continue;
        g[v][0]=min(P[X[v]],sum[0]-f[v][1]);
        g[v][1]=min(P[Y[v]],sum[1]-f[v][0]);
        get_g(v,u);
    }
    // 重标边权
    P[X[u]]=min(f[u][0],g[u][0]);
    P[Y[u]]=min(f[u][1],g[u][1]);
}
在转移 gg 的时候，可以先把 ∑v′∈SuLxv′+∑v′∈Sufv′,1\sum_{v' \in S_u}L_{x_{v'}} + \sum_{v' \in S_{u}}f_{v',1} 计算出来，转移的时候减掉 v′=vv' = v 的贡献就行，表示 v′≠vv' \not= v。

Part 3：环上最短路

（这个还要讲吗？）
对于所有的环分别考虑，然后破环成链。然后大概就是类似于下面的结构。
一个比较好的想法是维护从 11 号点出发，分别到达 (2,3,⋯ ,6,1)(2,3,\cdots,6,1) 这些点的前缀和，这样就可以维护蓝色的边了。
当然，也可以维护从 66 号点出发，分别到达 (5,4,⋯ ,1,6)(5,4,\cdots,1,6) 这些点的“后缀和”，这样就可以维护红色的边了。
由于经过 Part 2 的操作，同一个环上的两个点，最短路一定全在环上，并且是一个或者是两个区间和，所以在环上从 ii 到 jj 的最短路就可以由前缀和、后缀和数组求出了。
比如说，我们想求出来 2→52 \rightarrow 5 的最短路，在蓝色边上，就是求 [2,5][2,5] 的区间和，在红色边上，就是求 2→1→62 \rightarrow 1 \rightarrow 6 的边长和 6→56 \rightarrow 5 的边长之和，再对求出来的两个路径取 min⁡\min。
以下是求环上前缀和、后缀和以及求环上最短路的代码。
CPP
void get_pre_suf(){
    for(int i=1;i<=tot;i++){
        ll sum=0;
        pre[i].push_back(0);suf[i].push_back(0);
        for(int j=0;j<ring[i].size();j++){
            id[i][ring[i][j]]=j;
            // id 是一个 unordered_map，存一个 ring[i] 上的点在 ring[i] 的下标
            if(j&1)sum+=P[ring[i][j]];
            else sum+=R[ring[i][j]];
            //环上的路径是 R、P 交替的
            pre[i].push_back(sum);
            suf[i].push_back(0);
        }
        sum=0;
        for(int j=ring[i].size()-1;j>=0;j--){
            if(j&1)sum+=L[ring[i][j]];
            else sum+=P[ring[i][j]];
            suf[i][j]=sum;
            //由于是建立虚点，这里的 +1 可以看作避免负数的delta
        }
    }
}
ll ring_mindis(ll u,ll x,ll y){
    //在 u 为父亲节点的环中 x -> y
    //需要对 x 和 y 的大小分类讨论
    x=id[u][x],y=id[u][y];
    if(x<=y)return min(pre[u][y]-pre[u][x],suf[u][0]-suf[u][x+1]+suf[u][y+1]);
    else return min(pre[u][pre[u].size()-1]-pre[u][x]+pre[u][y],suf[u][y+1]-suf[u][x+1]);
}

Part 4：维护树上倍增矩阵

一般来讲，对于很多组询问，每次求出两两之间的最短路大抵就只有树，或者能够转换成树的图能够做到了。所以我们也是先考虑在树上做这件事。
树上求 p→qp \rightarrow q 的最短路，一般的思路是先找到 pp 和 qq 的最近公共祖先 uu，然后把 p→up \rightarrow u 与 u→qu \rightarrow q 的路径拼起来。
但是这个图和树还是有一些不同的，至少树上每一个点代表图上的两个点。那么在树上 p→qp \rightarrow q 的路径也不能只记一条，具体来讲，我们维护一个 2×22 \times 2 的矩阵，分别表示从 pp 表示的的左括号、右括号下标到 qq 表示的左括号、右括号下标的最短路径。我们不妨称其“路径矩阵”。
比如矩阵[a1a2a3a4]\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix}，a1,a2a_1,a_2 分别表示从 pp 表示的的左括号下标到到 qq 表示的左括号、右括号下标的最短路；a3,a4a_3,a_4 分别表示从 pp 表示的右括号下标到到 qq 表示的左括号、右括号下标的最短路。
现在我们考虑合并两个矩阵会发生什么。
设矩阵 [a1a2a3a4]\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} 表示 p→qp \rightarrow q 的路径，[b1b2b3b4]\begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \end{bmatrix} 表示 q→rq \rightarrow r 的路径，根据定义，p→rp \rightarrow r 的路径的矩阵是：[min⁡(a1+b1,a2+b3)min⁡(a1+b2,a2+b4)min⁡(a3+b1,a4+b3)min⁡(a3+b2,a4+b4)]\begin{bmatrix} \min(a_1+b_1,a_2+b_3) & \min(a_1+b_2,a_2+b_4) \\ \min(a_3+b_1,a_4+b_3) & \min(a_3+b_2,a_4+b_4) \end{bmatrix}。
发现这个和矩阵乘法非常像，就是把原本的乘法变成了加法，把原本的加法变成了取 min⁡\min。这个称为 (min⁡,+)(\min,+) 矩阵。
CPP
struct rect{
    ll num[2][2];
}zero,INF,getup[maxn][18],getdn[maxn][18];
rect operator *(rect a,rect b){
    rect c=INF;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c.num[i][j]=min(c.num[i][j],a.num[i][k]+b.num[k][j]);
            }
        }
    }
    return c;
}
现在考虑倍增。
由于我们需要“向上跳”，也需要“向下跳”，所以倍增数组也需要两个。也就是代码中的 getup 和 getdn。
我们先明确倍增数组的定义：
  • getup[u][i]：表示从 uu 开始，往上走 2i2^i 个节点所得到的路径矩阵。
  • getdn[u][i]：表示从 uu 往上走 2i2^i 个节点所得到的点，走到 uu 的路径矩阵。
  • up[u][i]：LCA 数组。
倍增的预处理首先要赋初值。但是也很简单，把所有“父亲-儿子”的结构都处理一遍就行。由于“父亲-儿子”在图中一定在一个环内，所以直接套用环上最短路查询。
以下是预处理倍增的代码。
CPP
void initdfs(ll u,ll fat){
    fa[u]=fat;
    dep[u]=dep[fat]+1;
    up[u][0]=fat;
    for(auto v:G[u]){
        if(v==fat)continue;
        rect uv;
        uv.num[0][0]=ring_mindis(u,X[v],X[u]);
        uv.num[0][1]=ring_mindis(u,X[v],Y[u]);
        uv.num[1][0]=ring_mindis(u,Y[v],X[u]);
        uv.num[1][1]=ring_mindis(u,Y[v],Y[u]);
        getup[v][0]=uv;
        uv.num[0][0]=ring_mindis(u,X[u],X[v]);
        uv.num[1][0]=ring_mindis(u,Y[u],X[v]);
        uv.num[0][1]=ring_mindis(u,X[u],Y[v]);
        uv.num[1][1]=ring_mindis(u,Y[u],Y[v]);
        getdn[v][0]=uv;
        initdfs(v,u);
    }
}
void initLCA(){
    initdfs(1,0);
    for(int j=1;j<18;j++){
        for(int i=1;i<=tot;i++){
            up[i][j]=up[up[i][j-1]][j-1];
            //路径合并顺序不能出错
            getup[i][j]=getup[i][j-1]*getup[up[i][j-1]][j-1];
            getdn[i][j]=getdn[up[i][j-1]][j-1]*getdn[i][j-1];
        }
    }
}
这样求出从 p→up \rightarrow u，以及从 u→qu \rightarrow q（其中 uu 是 p,qp,q 的最近公共祖先）的路径矩阵就简单很多了，先求出深度差，倍增合并路径矩阵即可。
但是从 p→qp \rightarrow q 的路径有的时候没必要经过 uu，实际上，走到 uu 所在的环中就得特殊处理了。所以实际上需要求出的深度差还需要减一，走到同一个环中就不用再往上走了。
以下是倍增求出路径矩阵的代码。
CPP
ll LCA(ll x,ll y){
    //我不信看这篇题解的人不会 LCA 怎么写
}
struct lcaitem{
    rect mar;//路径矩阵
    ll dn;//从 x->u 到达 u 所在环的第一个点
};
lcaitem getUP(ll u,ll y){
    //先向上走一步，因为这种矩阵运算没有单位元，防止合并矩阵时出错
    rect ret=getup[y][0];
    y=up[y][0];
    ll del=dep[y]-dep[u]-1;//这里少一步为了在同一个环内
    for(int i=0;i<18;i++){
        if(del&(1<<i)){
            ret=ret*getup[y][i];
            y=up[y][i];
        }
    }
    return {ret,y};
}
lcaitem getDOWN(ll u,ll y){//这个函数是同理的
    rect ret=getdn[y][0];
    y=up[y][0];
    ll del=dep[y]-dep[u]-1;
    for(int i=0;i<18;i++){
        if(del&(1<<i)){
            ret=getdn[y][i]*ret;//合并路径顺序要正确
            y=up[y][i];
        }
    }
    return {ret,y};
}

Part 5：处理询问

终于到了最后环节。但是是超级大分讨。
先说正常的 i→ji \rightarrow j 怎么做。先找到 ii 和 jj 在树上对应的点 pp 和 qq。
找到 uu 为 pp 和 qq 的最近公共祖先是必然的，然后对于 pp 向上找到到 uu 所在环的路径矩阵（记返回的点是 dnpdn_p），再对 qq 找到从 uu 所在环向下到 qq 的路径矩阵（记返回的点是 dnqdn_q），这些都是好做的。
然后分别枚举 dnpdn_p 取左括号、右括号下标和 dnqdn_q 取左括号、右括号下标，按照这样的枚举跑四边环上最短路，选择对应的矩阵上的数，最后取个 min⁡\min 就是答案了。
这一部分的代码如下：
CPP
ll getans(ll i,ll j){
    //ri 表示最开始的 i 是否值左括号，rj 表示最开始的 j 是否值左括号
    //这对选择合适的矩阵上的数有帮助
    bool ri=(ch[i]==')'),rj=(ch[j]==')');
    ll x=bl[i],y=bl[j];
    ll u=LCA(x,y);
    lcaitem xx=getUP(u,x),yy=getDOWN(u,y);
    rect xr=xx.mar,yr=yy.mar;
    ll dnx=xx.dn,dny=yy.dn;
    return min({ring_mindis(u,X[dnx],X[dny])+xr.num[ri][0]+yr.num[0][rj],
    ring_mindis(u,X[dnx],Y[dny])+xr.num[ri][0]+yr.num[1][rj],
    ring_mindis(u,Y[dnx],X[dny])+xr.num[ri][1]+yr.num[0][rj],
    ring_mindis(u,Y[dnx],Y[dny])+xr.num[ri][1]+yr.num[1][rj]});
}
当然这只是其中的一般情况，树上点的相对位置关系总是有许多 Corner Case。这里就列出我认为的一些 Corner Case。（我自己对这些边界情况处理不好，就导致这个函数的代码很长）
  1. ii 和 jj 在同一个环上。
  2. xx 是 yy 的祖先。
  3. yy 是 xx 的祖先。
  4. 令 uu 是 xx 和 yy 的最近公共祖先，并且 xx 的父亲是 uu。
  5. 令 uu 是 xx 和 yy 的最近公共祖先，并且 yy 的父亲是 uu。
注意不要轻易地交换 xx 和 yy，因为 x→yx \rightarrow y 和 y→xy \rightarrow x 的路径是不一样的。
大概我就判断了这些边界情况，这些边界情况与一般情况的代码实际上大同小异。

Part 6：代码

把以上所述拼接起来就得到了最终代码。时间复杂度 O(Klog⁡K+Qlog⁡K)O(K \log K+Q \log K)，常数较大。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn=1e5+10,inf=1e18;
ll TestCases,n,q;
char ch[maxn];
vector<ll> G[maxn],ring[maxn],pre[maxn],suf[maxn];//建树，挂到根的环，前缀和，后缀和
unordered_map<ll,ll> id[maxn];
ll f[maxn][2],g[maxn][2],dep[maxn],tot,cur,L[maxn],R[maxn],fa[maxn];
ll P[maxn],up[maxn][18],X[maxn],Y[maxn],bl[maxn],S[maxn],T[maxn];
struct rect{
    ll num[2][2];
}zero,INF,getup[maxn][18],getdn[maxn][18];
void init(){
    tot=cur=0;
    for(int i=0;i<=n+5;i++){
        id[i].clear();G[i].clear();ring[i].clear();pre[i].clear();suf[i].clear();
        f[i][0]=f[i][1]=g[i][0]=g[i][1]=0;
        dep[i]=L[i]=R[i]=fa[i]=P[i]=X[i]=Y[i]=bl[i]=S[i]=T[i]=0;
        for(int j=0;j<18;j++){
            up[i][j]=0;
            getup[i][j]=getdn[i][j]=zero;
        }
    }
}
struct lcaitem{
    rect mar;
    ll dn;
};
rect operator *(rect a,rect b){
    rect c=INF;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c.num[i][j]=min(c.num[i][j],a.num[i][k]+b.num[k][j]);
            }
        }
    }
    return c;
}
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);
}
void get_f(ll u,ll fat){
    ll sum[2]={R[X[u]],L[Y[u]]};
    for(auto v:G[u]){
        if(v==fat)continue;
        get_f(v,u);
        sum[0]+=R[Y[v]]+f[v][0];
        sum[1]+=L[X[v]]+f[v][1];
    }
    f[u][0]=min(sum[0],P[X[u]]);
    f[u][1]=min(sum[1],P[Y[u]]);
}
void get_g(ll u,ll fat){
    ll sum[2]={L[Y[u]]+g[u][0],R[X[u]]+g[u][1]};
    for(auto v:G[u]){
        if(v==fat)continue;
        sum[0]+=L[X[v]]+f[v][1];
        sum[1]+=R[Y[v]]+f[v][0];
    }
    for(auto v:G[u]){
        if(v==fat)continue;
        g[v][0]=min(P[X[v]],sum[0]-f[v][1]);
        g[v][1]=min(P[Y[v]],sum[1]-f[v][0]);
        get_g(v,u);
    }
    P[X[u]]=min(f[u][0],g[u][0]);
    P[Y[u]]=min(f[u][1],g[u][1]);
}
void get_pre_suf(){
    for(int i=1;i<=tot;i++){
        ll sum=0;
        pre[i].push_back(0);suf[i].push_back(0);
        for(int j=0;j<ring[i].size();j++){
            id[i][ring[i][j]]=j;
            if(j&1)sum+=P[ring[i][j]];
            else sum+=R[ring[i][j]];
            pre[i].push_back(sum);
            suf[i].push_back(0);
        }
        sum=0;
        for(int j=ring[i].size()-1;j>=0;j--){
            //0,1,2,3,4,5,6,7
            if(j&1)sum+=L[ring[i][j]];
            else sum+=P[ring[i][j]];
            suf[i][j]=sum;//这里的 +1 可以看作避免负数的delta
        }
    }
}
ll ring_mindis(ll u,ll x,ll y){
    //在 u 为父亲节点的环中 x -> y
    x=id[u][x],y=id[u][y];
    if(x<=y)return min(pre[u][y]-pre[u][x],suf[u][0]-suf[u][x+1]+suf[u][y+1]);
    else return min(pre[u][pre[u].size()-1]-pre[u][x]+pre[u][y],suf[u][y+1]-suf[u][x+1]);
}
void initdfs(ll u,ll fat){
    fa[u]=fat;
    dep[u]=dep[fat]+1;
    up[u][0]=fat;
    for(auto v:G[u]){
        if(v==fat)continue;
        rect uv;
        uv.num[0][0]=ring_mindis(u,X[v],X[u]);
        uv.num[0][1]=ring_mindis(u,X[v],Y[u]);
        uv.num[1][0]=ring_mindis(u,Y[v],X[u]);
        uv.num[1][1]=ring_mindis(u,Y[v],Y[u]);
        getup[v][0]=uv;
        uv.num[0][0]=ring_mindis(u,X[u],X[v]);
        uv.num[1][0]=ring_mindis(u,Y[u],X[v]);
        uv.num[0][1]=ring_mindis(u,X[u],Y[v]);
        uv.num[1][1]=ring_mindis(u,Y[u],Y[v]);
        getdn[v][0]=uv;
        initdfs(v,u);
    }
}
void initLCA(){
    initdfs(1,0);
    for(int j=1;j<18;j++){
        for(int i=1;i<=tot;i++){
            up[i][j]=up[up[i][j-1]][j-1];
            getup[i][j]=getup[i][j-1]*getup[up[i][j-1]][j-1];
            getdn[i][j]=getdn[up[i][j-1]][j-1]*getdn[i][j-1];
        }
    }
}
ll LCA(ll x,ll y){
    if(dep[x]>dep[y])swap(x,y);
    ll del=dep[y]-dep[x];
    for(int i=0;i<18;i++){
        if(del&(1<<i)){
            y=up[y][i];
        }
    }
    if(x==y)return x;
    for(int i=17;i>=0;i--){
        if(up[x][i]!=up[y][i]){
            x=up[x][i];
            y=up[y][i];
        }
    }
    return up[x][0];
}
lcaitem getUP(ll u,ll y){
    rect ret=getup[y][0];
    y=up[y][0];
    ll del=dep[y]-dep[u]-1;//这里少一步只是为了在同一个环内
    for(int i=0;i<18;i++){
        if(del&(1<<i)){
            ret=ret*getup[y][i];
            y=up[y][i];
        }
    }
    return {ret,y};
}
lcaitem getDOWN(ll u,ll y){
    rect ret=getdn[y][0];
    y=up[y][0];
    ll del=dep[y]-dep[u]-1;//这里少一步只是为了在同一个环内
    for(int i=0;i<18;i++){
        if(del&(1<<i)){
            ret=getdn[y][i]*ret;
            y=up[y][i];
        }
    }
    return {ret,y};
}
ll getans(ll i,ll j){
    bool ri=(ch[i]==')'),rj=(ch[j]==')');
    ll x=bl[i],y=bl[j];
    if(fa[x]==fa[y])return ring_mindis(fa[x],i,j);//corner case
    ll u=LCA(x,y);
    if(u==x){
        //case #1: x 是 y 的祖先
        if(x==fa[y])return ring_mindis(u,i,j);//corner case
        lcaitem st=getDOWN(u,y);
        rect r=st.mar;
        ll dn=st.dn;
        return min(ring_mindis(u,i,X[dn])+r.num[0][rj],
        ring_mindis(u,i,Y[dn])+r.num[1][rj]);
    }else if(u==y){
        //case #2: y 是 x 的祖先
        if(y==fa[x])return ring_mindis(u,i,j);//corner case
        lcaitem st=getUP(u,x);
        rect r=st.mar;
        ll dn=st.dn;
        return min(ring_mindis(u,X[dn],j)+r.num[ri][0],
        ring_mindis(u,Y[dn],j)+r.num[ri][1]);        
    }else{
        //case #3: 不存在祖先关系
        if(fa[x]==u){
            //corner case #1：x 的祖先是 lca
            lcaitem st=getDOWN(u,y);
            rect r=st.mar;
            ll dn=st.dn;
            if(ri)return min(
            ring_mindis(u,Y[x],X[dn])+r.num[0][rj],
            ring_mindis(u,Y[x],Y[dn])+r.num[1][rj]);
            else return min(
            ring_mindis(u,X[x],X[dn])+r.num[0][rj],
            ring_mindis(u,X[x],Y[dn])+r.num[1][rj]);
        }else if(fa[y]==u){
            //corner case #2：y 的祖先是 lca
            lcaitem st=getUP(u,x);
            rect r=st.mar;
            ll dn=st.dn;
            if(rj)return min(
            ring_mindis(u,X[dn],Y[y])+r.num[ri][0],
            ring_mindis(u,Y[dn],Y[y])+r.num[ri][1]);
            else return min(
            ring_mindis(u,X[dn],X[y])+r.num[ri][0],
            ring_mindis(u,Y[dn],X[y])+r.num[ri][1]);            
        }
        lcaitem xx=getUP(u,x),yy=getDOWN(u,y);
        rect xr=xx.mar,yr=yy.mar;
        ll dnx=xx.dn,dny=yy.dn;
        return min({ring_mindis(u,X[dnx],X[dny])+xr.num[ri][0]+yr.num[0][rj],
        ring_mindis(u,X[dnx],Y[dny])+xr.num[ri][0]+yr.num[1][rj],
        ring_mindis(u,Y[dnx],X[dny])+xr.num[ri][1]+yr.num[0][rj],
        ring_mindis(u,Y[dnx],Y[dny])+xr.num[ri][1]+yr.num[1][rj]});
    }
}
ll solve(){
    cin>>n>>q>>(ch+1);
    for(int i=1;i<=n;i++)cin>>L[i];
    for(int i=1;i<=n;i++)cin>>R[i];
    for(int i=1;i<=n;i++)cin>>P[i];
    ch[0]='(';ch[n+1]=')';
    R[0]=L[n+1]=P[0]=P[n+1]=inf;
    build_tree();
    get_f(1,0);
    get_g(1,0);
    get_pre_suf();
    initLCA();
    ll ret=0;
    for(int i=1;i<=q;i++)cin>>S[i];
    for(int i=1;i<=q;i++)cin>>T[i];
    for(int i=1;i<=q;i++){
        ll ss=getans(S[i],T[i]);
        ret+=ss;
    }
    init();
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    INF.num[0][0]=INF.num[0][1]=INF.num[1][0]=INF.num[1][1]=inf;
    cin>>TestCases;
    for(int i=1;i<=TestCases;i++){
        cout<<"Case #"<<i<<": "<<solve()<<"\n";
    }
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...