树分块学习笔记

· · 个人记录

树分块学习笔记

引言

在大多数时候，树上问题可以使用树剖、动态树和树分治进行解决，但在一些的特殊的情况下，或者在数据范围较为宽松的情况下，树分块也是一种不错的选择。

算法概述

和序列问题一样，树分块是一种暴力的暴力，大致思想就是将树上的点每次划分进 \sqrt{n}(或者基于题目性质的更优块大小)个块中，对与块内信息进行维护的算法。

而基于不同的题目，会有很多种不同的分块方法。在一般情况下，树分块在处理树的路径等具有连通性质的问题时表现较为强力。

法一：

按照 DFS 序进行划分，不能保证直径长度和块联通，一般用于处理子树信息，在处理其它信息时较为乏力。

法二：

检查当前节点的父亲所在块的大小，如果小于 \sqrt{n} 就把当前节点加入进去，不然新开块。块大小最坏 \sqrt{n}，可以保证块内联通和直径长度，是比较常用的分块方法。缺点是不能保证块的数量。

例题：

给定一棵树，树上每个点有一个权值，需要支持修改点权和查路径最小值。

经典的树剖/LCT 板子题，这里使用树分块解决：

按本方法分块，对于每个点记录它到块内深度最小的点路径上的答案。

查询时会在 LCA 处多出一个零散快，需要注意。

修改直接修改块内答案即可。

复杂度 O((n+q)\sqrt{n})

法三：

随机找 \sqrt{n} 个关键点，对于所有点找到它的第一个关键祖先，将它和关键祖先分为一块。可以保证块联通，在期望下块直径长度和块大小为 \sqrt{n} ，缺点是常数较大。

例题：

bzoj2589/SP10707 Count on a tree II

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v)，你需要回答u xor lastans和v这两个节点间有多少种不同的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

这个题就是该分块方法的经典应用，因为我们想要块联通且块数量不超过 \sqrt{n}。

这个题的解题方法也有很多，这里提供其中一种。

我们分块以后的每个询问被拆成了两个零散块和一个整块，我们记两个零散块所构成的集合分别为 A 和 B，整块构成的集合为 C，那么答案就为 |A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|。

然后发现 |A|,|B|,|A\cap B|,|A\cap B\cap C| 可以在处理零散块的时候直接计算，剩下的可以 O(n\sqrt{n}) 预处理。

复杂度 O((n+q)\sqrt{n})。

法四：

引题：

[SCOI2005]王室联邦

　“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成 员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条 直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个 城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经 过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。聪明的 你快帮帮这个国王吧！

方法：按 dfs 逆后序入栈，如果当前节点的子树大小大于 B 就暴力合并。

感觉讲的有点抽象，可以结合代码理解：

void dfs(int x,int fa){
    int now=ls;
    for(rg int i=head[x];i;i=e[i].nxt){
        int y=e[i].node;
        if(y==fa)continue;
        dfs(y,x);
        if(ls-now>=B){
            rt[++ans]=x;
            while(ls>now){
                bl[s[ls]]=ans;
                ls--;
            }
        }
    }
    s[++ls]=x;
}

这个方法可以很好地结合树上莫队进行使用。

结语

希望大家可以在本篇博客中略有收获吧。