浅析 OI 中的树上信息维护

· · 个人记录

顺道推几个以前写的东西。

一些（可能？）有用的东西 & 思想和二级结论（还在更）

【洛谷日报 #427】浅谈网络流的各种建模技巧

一些没用的话

树树题感觉是做起来最舒服的题啊！

树结构无论在 OI 中还是在现实中都极为普遍——自然界的树、叶脉、根系、物种的进化。族谱，社会的组织阶级。人猿相揖别。分治的思想，搜索树，蒙洛卡特。甚至星系和超星系团。

我会说，整个世界都是一棵树。

\textbf{Introduction}

本文将简单讨论树的性质和一些树上信息的维护方法。同时也将结束我个人在 2024 年对树结构的学习。当然也有可能讨论一些并非严格的树结构（但跟树相似）的图，比如基环树和仙人掌。本文不是算法入门博客，在阅读本文前确保至少会基础的树和数据结构。

树，简单来说就是不存在简单环的无向联通图。

对于一张图，判定它是树，除了上述条件，可以从下面角度看：

  2. 所有结点两两之间有且只有恰好一条简单路径到达的无向图（所有边都为割边的图）。

树的特殊结构使得我们通常能够在树上以非常优秀的复杂度，解决原本在一般图上困难的问题。

比如树的全源最短路，可以做到 \Theta(n)/\Theta(1) 解决，而在一般图上我们找一个 n^2 的算法都已经相当困难。

图的最小 & 最大生成树、边双缩点、圆方树、最短路树、序列的笛卡尔树、失配树和 ACAM 的 fail 树、SAM 的 parent tree······，这些都是我们将一些图上问题转化为树上问题的方法。

同样，树本身极好的性质也在帮助着我们优化算法和数据结构。

\textbf{Main Text}

树的结构有强力的分治特性。

一般来讲，树上问题分路径问题和子树问题。路径问题比如 LCA，k 级祖先以及一些乱七八糟的路径统计。子树问题比如一些树上 dp 优化，换根之类的。

我们维护树的结构有一些强力工具。

擅长维护路径统计，以及跟一个点联通的联通块统计。

经典题：幻想乡战略游戏，成都七中。

我们熟悉的轻重链剖分、长链剖分、DSU on tree、全局平衡二叉树、Link Cut Tree、静态 Top Tree。

一个重要的理论基础就是，轻子树大小之和是 \Theta(n \log n) 级别的，这就是启发式合并在树上的体现（启发式合并真的到处都在用）。

优点是极具普适性，几乎所有树上 ds 问题都能用链分治平替。而且链分治本身就有不少很好的性质。事实上，你非常难找到不能链分治，而只能点分治或线段树合并的题。

强力工具：树上动态 dp（全局平衡二叉树维护这个东西极其方便）。

一般维护子树问题更强力，但是有时候维护路径问题有奇效。比如 dfs 序 & 欧拉序求 LCA。

同样强于维护子树问题，而且往往链分治的题目存在类似做法。

整体 dp，树上的 slope trick，闵可夫斯基和等。

对于一类难以 poly log 的问题，我们有树上的分块。大概能随机撒点，或者王室联邦分块。

不过直接对点分块有些性质是比较难保持的，这就是引入树收缩理论的原因。

以及有个强大的，Top Cluster 分块。

比较特殊。

树上信息

我们在树上到底要维护什么信息？

很简单，阅读 [NOI2022] 树上邻域数点 即可。

一般来讲，我们在树上维护这些结构：

链分治

树上问题往往有一种困境，就是我们在序列上可以（简单）解决的问题，放到了树上就变得不那么好做了。

由于树跟序列的形状是比较相似的，序列就是退化为链的树。

而我们在序列上通常有优秀的算法和数据结构解决我们的问题，比如线段树维护区间双半群信息。我们更希望看到序列，而并不是性质更弱的树。

『链剖分』

对于树，我们想要将树拆分为若干条不交的，一条链内部只有祖先后代关系的链。

至于为什么要不交且一条链内只有祖先后代，首先信息并不总是可以重复覆盖的，链如果可交的话并不方便我们维护信息。同样我们钦定这些链必须有且只有祖先后代关系（一条链内深度必定是不交的值域连续段）。

观察这样有什么好处，我们显然可以断言任意结点都最多会有一个直接儿子是它的后继，使得它们在一条链中。

我们将 u 到后继的边称为重边（实边，偏爱儿子），将除了这类边之外的边都称为轻边（虚边，非偏爱儿子）。

利用 dfs 序的连续性，我们 dfs 的时候优先 dfs 进后继里面，那么一条重链在 dfs 序上形成连续的区间。

对于树结构静态的树上路径问题，『重链剖分』 告诉我们了一种将树拆分成一堆 「重链」 的方法。即将后继设置为子树大小最大的子树，使得任意结点跳到任意祖先，最多经过 \log 段不同的重链。原因是 u 每次跳一次轻边，u 的子树大小至少乘二。

直接强行将链看作序列维护，那么对于一般的双半群信息维护，我们就可以用线段树做到 \Theta(\log^2 n) 的链修改链查询和 \Theta(\log n) 的子树修改子树查询。

实际上我们可以相对轻松的做到链修改和链查询的单 \log。

重链剖分本身是很优秀的剖分方式，我们真正的复杂度瓶颈在于数据结构跟重链剖分很不搭配。在数据结构上面我们花费了太长的时间。

在普通的序列数据结构上，我们会将每个区间看作平等的，但是在重剖的链分治结构上，有一些区间可能永远不会出现。

想一想为什么 LCT 是 \Theta(n \log n) 的。LCT 有一点开创性就是，我们可以考虑用一棵比较任意的二叉树结构维护每条实链，虚边上下认父不认子，中序遍历实链二叉树深度递增。

我们的链剖分方法已经足够优秀，剩下的只是每条链上的数据结构问题。

于是全局平衡二叉树就出现了，对于每条重链，我们按轻子树大小作为权值，按新的带权中点分治建树。

从任意一个点开始，每次跳父亲（实链二叉树和虚边意义下的），最多跳 \Theta(\log n) 次到根。

因为每跳一次父亲，所在子树大小至少翻倍。

那么我们直接定位到点，按照我们平衡树维护区间信息那样先跳到 LCA，顺便修改维护，到 LCA 了直接定位区间，修改并 \text{pushup} 即可。

时间复杂度 \Theta(n \log n)。

一般用来优化动态 dp，以及高复杂度 pushup 的树剖线段树。因为理论复杂度优势使得它能够在这些应用场景下跑得比树剖快很多，但一般情况下（尤其是树剖用树状数组维护等），不会比树剖快多少。

这东西直接修改 u \leadsto v 的话写起来比较便秘，但是如果直接修改到根那完全很好写。

void mdf(int x, int y) {
    a[x] = y;
    for (; x; x = fa[x]) {
        if (!fa[x] || ls[fa[x]] == x || rs[fa[x]] == x) up(x);
        else {
            rep(i, 0, m - 1) h[fa[x]][i] = h[fa[x]][i] / (ad(t[x].c[i], 1) % mod), s[fa[x]][i] = sb(s[fa[x]][i], t[x].d[i]);
            up(x);
            rep(i, 0, m - 1) h[fa[x]][i] = h[fa[x]][i] * (ad(t[x].c[i], 1) % mod), s[fa[x]][i] = ad(s[fa[x]][i], t[x].d[i]);
        }
    }
}

切树游戏代码片段。

『DSU on tree』

顾名思义，树上启发式合并。

简单来说，如果对于子树信息/链信息（链信息我们就枚举 LCA 为 u），我们如果能低复杂度继承一个儿子的结构。那么就可以先计算轻儿子的贡献，但是不保留它们在数据结构上的修改，计算重儿子的贡献并继承重儿子的修改，然后暴力将轻儿子纳入修改。时间复杂度是轻子树大小之和，也就是 \Theta(nf(n) \log n + g(n)n)，f(n) 是进行修改的复杂度，g(n) 是继承的复杂度。

关于轻子树大小之和为什么是 \Theta(n \log n)：每个点作为轻儿子被统计一次，那么其所在联通块大小至少乘二，所以最多作为轻儿子被统计 \Theta(\log n) 次。

我们发现这本质就是不改变重儿子，然后将轻儿子信息合并到重儿子上。

这么说，将启发式合并写成树结构，那么这就跟 DSU on tree 所做的事情一模一样。

经典题：CF600E（被做烂了都）。

DSU on tree 极容易维护静态子树问题，因为这种时候继承一个儿子一般都容易做到低复杂度，然后对于轻儿子只是 \Theta(n \log n) 次对数据结构的修改。

除了部分整体 dp 题，DSU on tree 经常能平替树上线段树合并。

简单来说，钦定 LCA，对于一个点 u，我们只关心它在 LCA 的不同子树的前驱后继（定义在编号上的前驱后继）。

发现这样的前驱后继对数不会超过轻子树大小（毕竟至少有一个点来自轻子树），于是有用的前驱后继数不超过 \Theta(n \log n) 个。把这些点对搜出来后问题只是简单的扫描线树状数组。

因此 DSU on tree 在处理树上支配问题时效果很显著，典型例子 [NOIP2024T4] 树上查询。

我叫它 rldcot 支配，表现为钦定 LCA 的时候，有些点跟不同子树较少的点配对就可以计算出答案。

树上启发式分裂在 [NOI2024D2T2]登山 中大显身手。

对于它序列化的改造，P4755 是一个极好的例子。在钦定中心元素（比如最值），进行分治的过程中，我们根据元素较少的那边为基准，开数据结构统计信息。对于最值分治，就是对笛卡尔树的树上启发式分裂。

tips：笛卡尔树真的很好用，一些序列上跟最值相关的问题，很适合考虑笛卡尔树。

还有一个板子是 ABC282H。

『长链剖分』

将选取重儿子的标准从子树大小改为子树内最深的结点深度即可。

合并深度相关的问题时，如果复杂度是子树深度之和，那么可以考虑继承长儿子，暴力短儿子。

复杂度是短儿子的最深深度之和的，看起来不对，但事实上考虑每个结点只会在第一个长链产生贡献。因为结点 u 任意一个祖先所在的长儿子最深深度显然大于 u 的深度。

一个得到的较弱的结论是 k 级祖先所在的长链长度一定大于等于 k。

树上 k 级祖先（LA）： 对于每个长剖顶点，求出向下（链上的儿子）向上长链长度的祖先存进线性表里，先求出树上倍增数组，然后倍增到 w = 2^{\lfloor \log_2 k \rfloor} 级祖先 p。

考虑 d = k - w，跳到 p 的链头，考虑向上还是向下，直接查表即可。时间复杂度 \Theta(n \log n)/\Theta(1)。

tips：LA 存在 \Theta(n)/\Theta(1) 做法。

优化 dp 的经典例子是 P5904 [POI2014] HOT-Hotels 加强版。

还有一个经典例子：P4292 [WC2010] 重建计划。