Brief description:
给定一棵树,每个节点要么是黑色,要么是白色,能执行两个操作:
。。。把某一个点取反色,返回距离最远的黑色点对。
Analysis:
。。。… 。。链分治和边分治的方法参见 Qtree 4 那篇。。)
。。这里记录一下括号序列的方法。。。)
定义一种对一棵树的括号编码。这种编码方式很直观,所以,这里不给出严格的定义,用以下这棵树为例:
(图片自行脑补。。。)
可以先序遍历后写成:[A[B[E][F[H][I]]][C][D[G]]] 去掉字母后的串:[[[][[][]]][][[]]]就称为这棵树的括号编码。(这个编码本质上是由深度优先遍历得到的)
考察两个结点,如 E 和 G ,取出介于它们之间的那段括号编码 :][[][]]][][[ 把匹配的括号去掉,得到:]][[我们看到 2 个 ] 和 2 个 [,也就是说,在树中,从 E 向上爬 2 步,再向下走 2 步就到了 G。
注意到,题目中需要的信息只有这棵树中点与点的距离,所以,贮存编码中匹配的括号是没有意义的。
因此,对于介于两个节点间的一段括号编码 S,可以用一个二元组 (a, b) 描述它,即这段编码去掉匹配括号后有 a 个 ] 和 b 个 [。
所以,对于两个点 PQ,如果介于某两点 PQ 之间编码 S 可表示为 (a, b),PQ 之间的距离就是 a+b。
也就是说,题目只需要动态维护:max{a+b | S’(a, b) 是 S 的一个子串,且 S’ 介于两个黑点之间},
这里 S 是整棵树的括号编码。我们把这个量记为 dis(s)。现在,如果可以通过左边一半的统计信息和右边一半的统计信息,得到整段编码的统计,这道题就可以用熟悉的线段树解决了。
这需要下面的分析。
考虑对于两段括号编码 S1(a1, b1) 和 S2(a2, b2),如果它们连接起来形成 S(a, b)。
注意到 S1、S2 相连时又形成了 min{b, c} 对成对的括号,合并后它们会被抵消掉。(?..这里 b, c 应该分别是指 b1 和 a2。。。所以:
当 a2 < b1 时第一段 [ 就被消完了,两段 ] 连在一起,例如: ] ] [ [ + ] ] ] [ [ = ] ] ] [ [ 当 a2 >= b1 时第二段 ] 就被消完了,两段 [ 连在一起,例如: ] ] [ [ [ + ] ] [ [ = ] ] [ [ [ (?..反了?。。。
这样,就得到了一个十分有用的结论:
当 a2 < b1 时,(a,b) = (a1-b1+a2, b2), 当 a2 >= b1 时,(a,b) = (a1, b1-a2+b2)。由此,又得到几个简单的推论:
(i) a+b = a1+b2+|a2-b1| = max{(a1-b1)+(a2+b2), (a1+b1)+(b2-a2)} (ii) a-b = a1-b1+a2-b2 (iii) b-a = b2-a2+b1-a1由 (i) 式,可以发现,要维护 dis(s),就必须对子串维护以下四个量:
right_plus:max{a+b | S’(a,b) 是 S 的一个后缀,且 S’ 紧接在一个黑点之后} right_minus:max{a-b | S’(a,b) 是 S 的一个后缀,且 S’ 紧接在一个黑点之后} left_plus:max{a+b | S’(a,b) 是 S 的一个前缀,且有一个黑点紧接在 S 之后} left_minus:max{b-a | S’(a,b) 是 S 的一个前缀,且有一个黑点紧接在 S 之后}这样,对于 S = S1 + S2,其中 S1(a, b)、S2(c, d)、S(e, f),就有
(e, f) = b < c ? (a-b+c, d) : (a, b-c+d) dis(S) = max{dis(S1), left_minus(S2)+right_plus(S1), left_plus(S2)+right_minus(S1), dis(S2)}那么,增加这四个参数是否就够了呢?
是的,因为:right_plus(S) = max{right_plus(S1)-c+d, right_minus(S1)+c+d, right_plus(S2)} right_minus(S) = max{right_minus(S1)+c-d, right_minus(S2)} left_plus(S) = max{left_plus(S2)-b+a, left_minus(S2)+b+a, left_plus(S1)} left_minus(S) = max{left_minus(S2)+b-a, left_minus(S1)}这样一来,就可以用线段树处理编码串了。实际实现的时候,在编码串中加进结点标号会更方便,对于底层结点,如果对应字符是一个括号或者一个白点,那 么right_plus、right_minus、left_plus、left_minus、dis 的值就都是 -maxlongint;如果对应字符是一个黑点,那么 right_plus、right_minus、left_plus、left_minus 都是 0,dis 是 -maxlongint。
现在这个题得到圆满解决,回顾这个过程,可以发现用一个串表达整棵树的信息是关键,这一“压”使得线段树这一强大工具得以利用.. .
———— 以上摘自 NOI08 冬令营论文 《数据结构的提炼与压缩》 by cqx 。。。
线段树维护括号序列(2s+- ...
链分治(2.5s+ ...
边分治。(23.0s++
External link:
http://www.lydsy.com/JudgeOnline/problem.php?id=1095
http://hi.baidu.com/wjbzbmr/blog/item/2b02ec1cda7abbfa1ad57656.html