题解：AT_arc173_d [ARC173D] Bracket Walk

不是很难但需要人类智慧的题，没见过这个 trick 感觉一步都不会。。。

首先有一个结论：对于一个左括号数量等于右括号数量的括号序列，其一定存在一个循环位移是合法的括号序列。

证明的话直接把 ( 当作 $1$ 把 ) 当作 $-1$ 找到前缀和最小的那个位置作为起点就可以了。

在图上把 ( 当作 $1$，) 当作 $-1$，有了这个结论之后直接可以把第 $3$ 个限制转化为找到图上一个包含所有边的环使得这个环的边权为 $0$。

类似于 [WC2011] 最大XOR和路径 的思想，将环视作若干个简单环的拼接，每个环的权值可以被加上任意多次。所以实际上是要所有环的一个线性组合是的这个线性组合的权值等于 $0$。这个条件满足如果无法满足显然是所有环都是正环或所有环都是负环。用 SPFA 或什么算法判一下正负环即可。

时间复杂度 $\operatorname{O}(nm)$。