Luogu7323 [WC2021] 括号路径

发表于 更新于 分类于 ， ， 阅读次数：

题意：给出一张 个点的有向图，有 个括号类型，图的每条边上可能有一个左括号或右括号，种类为 之一。记一条边 表示 到 有一条有向边，其中的括号种类为 。

用 次加边操作来建立这张图。每次加边操作如下：

  • 给出 ，建立 和 。

问有多少个无序点对满足它们中的一条有向路径的括号连成的字符串是一个合法括号匹配串。

，，时限 。

本题有一个非常关键的性质 ： 和 总是成对出现的。

联系本题是 T1 的事实，应当大胆发掘性质。

不难发现，任何一条合法的括号路径，反向后仍然存在对应的合法括号路径。即 ： 如果 合法，那么 也合法。

进一步地，若 合法，则 也合法。

综上，我们只需求出图中有多少个联通块，连通块内部的任意点对都是合法的，其他点对均不合法。

若点 存在两条出边 ，且 是右括号（即 ），则 是合法路径，于是可以将 合并成一个点处理。

当找不到这样的路径时，显然图中不再有任何合法路径。

维护时，用动态开点线段树（按照 ）维护某个点的出边集合，合并时若叶子重叠则出发新合并。

复杂度为 。