Static Top Tree(静态顶树?)

在刷AtCoder Beginner Contest 351时遇到这题：G - Hash on Tree，没能做出来，看题目描述感觉好像也不是太复杂的样子，但是看了题解之后，瞬间感觉这道题一点都不Beginner，题解中提到了一个Static Top Tree的数据结构，搜了一下基本没搜到什么直接的资料，看了题解感觉理解起来也非常困难，便想着用自己的语言记录下来，方便后续复习。

Static Top Tree

Static Top Tree是一颗深度为$O(logN)$的二叉树，它可以用来描述子树之间的合并。

为了描述怎样构建一个Static Top Tree，我们先描述合并的反过程，分解一棵树：

• 首先对这棵树进行HLD(Heavy Light Decomposition)分解，关于HLD，可以参考：https://usaco.guide/plat/hld?lang=cpp

  假设HLD之后树的结构如下所示：
  

• 然后重复执行下面的4个步骤：

  • 选择连接root的Heavy Path，移除Path上的所有Heavy Edges
    
  • 上一步之后，可能会出现多棵子树，每棵子树的根节点都只剩下Light Edges连接着，将该根节点移除，注意对应的Light Edges仍然保留，这些边认为连接着一个虚拟节点
    
  • 将以虚拟节点为根的子树分离，拷贝虚拟节点作为每棵新子树的根
    
  • 将上一步每棵子树的虚拟节点移除，成为一颗普通的子树（包含一条连接着Root的Heavy Path，或者是一个单独的节点）
    

画几张图来直观感受下原本的树在Static Top Tree中的结构，左边的树为原始树，右边的树为构建出的Static Top Tree

• 一条链的情况（深度为$O(N)$）
  
• 所有节点的父节点为同一个节点（宽度为$O(N)$）
  
• 更一般的情况
  

代码实现与讲解

按照将Heavy边路径的节点分解，并按照处于Heavy路径上的节点数二分来构建Static Top Tree，时间复杂度为$O(log^2N)$，因为一条从根到叶子节点的路径上，Heavy边最多有$O(logN)$段，而每段Heavy边构建的完美二叉树高度为$O(logN)$，所以累积复杂度为$O(log^2N)$

按照题解中的描述，构建二叉树时按照处于Heavy路径上的节点为根的整棵子树的节点数来二分，而不只是根据处于处于Heavy路径上的节点数本身来二分，可以将树的高度优化为为$O(logN)$，从而使时间复杂度变为$O(logN)$，题解中略过了证明，我直觉地感觉他说的是对的，但我也不会证明。

AtCoder Beginner Contest 351 G - Hash on Tree 题解

这道题最难的部分就是在于怎么描述compress操作

以下图所示的数据举例，下图中节点的值等于节点的标号

Path Cluster中有2个值a和b

• a: 在该Cluster中，所有Light边连接的节点，以该节点为根的所有子树的乘积
  • 例如上图中，Static Top Tree中的17节点表示1,2,4,10,3,8已经合并，2,5还未合并，此时17节点的a值为440，表示4,10,3这3个节点为根的子树的乘积
• b: 在该Cluster中，以最上层的Heavy边的父节点作为根节点，连续的Heavy边路径中，如果Heavy边已经合并，则该节点为根的整颗子树都已经合并，如果Heavy边未合并，则到该节点为止的树的值；
  • 例如上图中，Static Top Tree中的17节点表示1,2,4,10,3,8已经合并，2,5还未合并，此时17节点的b值为81，表示1,2,4,10这颗树的值

compress p,c操作，合并的必定是一条Heavy边，p离根节点更近：

• p.a = p.a * c.a
• p.b = p.a * c.b + p.b

进行compress操作时，下面的节点沿着Heavy边向上合并，由于向上的路径都是Heavy边，进行的操作是+，Heavy边上的完整计算已经完成，放在了p.b中，路径上Heavy边相邻的边都为Light边，进行的操作是*，路径中相邻节点所有的乘积乘起来放在了p.a中，下面的子树的c.b需要乘以上层所有相邻的节点，即p.a