【听课笔记】点分治/点分树相关

似乎主要是点分治的相关内容?

简单的前言

首先对于树的点分治所要解决的问题和普通分治一样,只需要统计经过分治中心的信息,假设对于 $k$ 个点而言,统计经过分治中心的信息复杂度是 $O(\gamma(k))$ 的,那么最后的总复杂度就是 $\gamma(n)\log n $ 。

对于树的边分治而言,遇到菊花就会崩掉。于是考虑对每个点进行三度化 ,意即建立虚点使得每个点的度数都不超过 $3$ (二度化之后要么是链要么是环)。这样最终的 $size=k$ 的一层至多会分成一个 $size=\frac{1}{3}k$ 的和一个 $size=\frac{2}{3}k$ 的,可以知道如果度数 $\leq 3$ ,这就是能做到的最佳上界。于是最后的复杂度大概是 $\gamma(k)\log _{\frac{3}{2}}k$ 。

嗯,可能边分治就只用来分析个复杂度,好像几乎没人用的样子。不过也有个好处吧,就是不用考虑可能存在的分治中心的边界问题。

常见点分治

比较常见的数据结构

一般这个东西都比较显然…就题论题吧。

如果信息可以容斥

这一类比较常见的是统计满足某个有可减性的点对数,比如统计路径长度/点权和 $<k$ 的路径。常规的容斥做法是考虑对于每一层,计算出所有可能的点对,并且减去那些 belong(x)=belong(y) 的点对 $(x,y)$ 。

类哈夫曼树合并

每次选择两个size最小的子树进行合并,这样最后合并的总复杂度摊下来也是 $n \log n$ 的。这个主要用于那些不容易插入删除但是容易合并/重构的信息统计。注意到必须是从小合并到大,这样每次已合并的两个集合 $size$ 至少是较小的那个的两倍,所以每个点至多合并 $\log n$ 次……

以上复杂度分析似乎很有问题。我也不知道该怎么去定量分析这个问题。

不过uoj群给了一种很妙的证法。就是考虑每次选两个最小的合并一定可以达到复杂度的下界,因为对于一个合并顺序 $a<b<c$,merge(a,b)merge(b,c) 的复杂度是 $O(2(a+b)+c)$ ,改变合并顺序,merge(a,c)merge(b,c)的 复杂度是 $O(2(a+c)+b)$,也就是改变这个顺序至少不会更优。所以如果想要证明这种合并方式优于某个复杂度,那么只需要随便构造一个这种复杂度的合并方式即可。

那么问题转化到了如何构造一种 $n\log n$ 的合并。发现如果每次分成差不多大小的两堆,那么复杂度的递推式就是

但是这种分析的方式存在一定的问题,就是单纯这么写很容易构造出 $O(n)$ 层,但是 $O(n)$ 层是不符合「每次分成差不多两堆递归」这种情况的。

然后 uoj (没错我啥都不会只能到处问)里的神仙定量分析了一波,感觉十分有道理。大概就是考虑如果存在某个物品的大小 $\geq \frac{1}{3}$,那么直接把这个物品单独拿出来分成一部分,剩下的分成一部分;否则如果全部的物品的 $size$ 都 $<\frac{1}{3}$ ,那么必定可以分出一堆 $\frac{n}{3}\leq size<\frac{2n}{3}$ 的物品,原因在于这种情况下至少有 $>3$ 种物品,那么如果物品再多的话,只能是类似于把之前的某个物品拆分(总体积不变且每个物品至多大小为 $\frac{1}{3}$)。而在三个物品的时候,是一定可以划分出 $\frac{n}{3}$ 来的,并且物品数如果增多,那么由于体积减小一定可以让划分更平均。所以上界是

算出来复杂度就是 $O(n\log_{\frac{3}{2}} n)$ 。

嗯,但是这样似乎并不能证明随机选两堆合并的复杂度…那就期望 log 吧!

一堆题

限制距离的点对数

求距离不超过 $k$ 的点对数。

注意到可以用点分治,分治的时候只需要考虑经过分治中心的路径,这就显然是枚举每棵子树,套一个树状数组就做完了。直接合并似乎不是很简单。所以还是一个点一个点地插入写起来比较简单一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
void make_root(int x, int fa){
size[x] = g[x] = 1 ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa && !vis[to(k)]){
make_root(to(k), x) ;
size[x] += size[to(k)] ;
g[x] = max(g[x], size[to(k)]) ;
}
chkmax(g[x], num - g[x]) ;
if (g[x] < g[rt]) rt = x ;
}
void dfs(int x, int fa, int v){
size[x] = 1 ;
if (fa == rt)
son[++ cnt] = x, lst[x] = v ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa && !vis[to(k)])
dfs(to(k), x, val(k)), size[x] += size[to(k)] ;
}
int tot ;
int buc[N] ;
int low(int x){ return x & (-x) ; }
void add(int x, int v){
for ( ; x <= k ; x += low(x)) buc[x] += v ;
}
ll ask(int x){
ll ret = 0 ;
for ( ; x ; x -= low(x)) ret += buc[x] ;
return ret ;
}
void calc(int x, int fa, int dx){
if (dx > k) return ; d[++ tot] = dx ;
for (int k = head[x] ; k ; k = next(k))
if (!vis[to(k)] && to(k) != fa)
calc(to(k), x, dx + val(k)) ;
}
void solve(int root){
cnt = 0 ;
vis[root] = 1 ; tot = 0 ;
rt = root ; dfs(root, 0, 0) ;
// cout << root << '\n' ; debug(son, 1, cnt, '\n') ;
for (int i = 1 ; i <= cnt ; ++ i){
int otot = tot ; calc(son[i], 0, lst[son[i]]) ;
// for (int j = otot + 1 ; j <= tot ; ++ j) cout << d[j] << " " ; puts("") ;
for (int j = otot + 1 ; j <= tot ; ++ j) ans += (ll)ask(k - d[j]) ;
for (int j = otot + 1 ; j <= tot ; ++ j) add(d[j], 1) ;
}
ans += ask(k) ; // cout << root << " " << ans << endl ;
for (int i = 1 ; i <= tot ; ++ i) add(d[i], -1) ;
for (int k = head[root] ; k ; k = next(k))
if (!vis[to(k)]) num = size[to(k)], make_root(to(k), rt), solve(to(k)) ;
}
int main(){
int u, v, w ;
cin >> n ; g[0] = n ;
for (int i = 1 ; i < n ; ++ i){
cin >> u >> v >> w ;
add(u, v, w), add(v, u, w) ;
}
cin >> k ; num = n ;
make_root(1, 0) ; solve(rt) ;
cout << ans << '\n' ; return 0 ;
}

好久没写了,感觉写起来还可以。

括号序列问题

树上每条边有一个括号,统计有多少合法的括号序列路径。

还是直接点分,之后将从 $root$ 延伸出的链中,左括号未匹配的和右括号未匹配的个数相同的可以配对。于是就记一下当前分治中心到各个子树内每个点路径上的匹配值( ( 贡献为1, ) 为 -1)。然后拿个桶维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void calc(int x, int fa, int dx){
d[++ tot] = dx ; q[tot] = x ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa && !vis[to(k)])
calc(to(k), x, dx + val(k)) ;
}
void solve(int root){
vis[root] = 1 ;
tot = 0 ; dfs(root, 0, 0) ;
for (int i = head[root] ; i ; i = next(i)){
if (vis[to(i)]) continue ;
int ot = tot ; calc(to(i), root, val(i)) ;
for (int j = ot + 1 ; j <= tot ; ++ j)
ans += (ll)buc[- d[j] + M / 2] ;
for (int j = ot + 1 ; j <= tot ; ++ j)
buc[d[j] + M / 2] ++ ;
}
// cout << root << " " << ans << endl ;
// for (int i = 1 ; i <= tot ; ++ i)
// cout << d[i] << " " << q[i] << " & " << endl,
for (int i = 1 ; i <= tot ; ++ i) buc[d[i] + M / 2] = 0 ;
for (int k = head[root] ; k ; k = next(k)){
if (!vis[to(k)]){
num = size[to(k)] ; rt = 0 ;
make_root(to(k), rt) ; solve(rt) ;
}
}
}

路径数量问题

给定一棵树,求长度分别为 $1,2,3\ldots n$ 的路径数量。

发现可以对每个子树记一下 $buc_i$ 表示深度为 $i$ 的点的数量,发现两棵子树的 $buc$ 对答案的贡献是一个卷积的形式。那么考虑直接枚举每棵子树,计算贡献时对当前桶和前缀桶用 $\rm NTT$ 来合并即可。

值得注意的是,这东西必须要从小到大枚举每个子树进行合并,复杂度才是对的(证明就是上面那个类哈夫曼树合并的证明)

最终复杂度 $n\log ^2 n$ 。代码就不写了,就是死亡二合一罢了。

树上背包问题

给定一棵树,树上每个点有一个权值一个重量。要求选择一个连通子树,使得重量和小于某个给定的 $V$ 且权值和最大。

$n\leq 5000,V\leq 3000$

据说是经典套路题,但我不会…

考虑强制选根怎么做。考虑直接树形dp,合并两个子树的背包复杂度是 $V^2$ 的。于是考虑换一种可以不去合并子树的 $dp$ 方式。考虑在 dfs 序上对这个东西进行dp,设一个点 $u$ 子树的范围是 $p_u\sim r_{u}$ ,那么就可以设 $f_{i,v}$ 表示考虑了 $i\sim n$ 的物品,根必选且容积为 $v$ 的最大价值。考虑转移,对于一个 $i$ 而言,如果选了他,就可以从 $i+1$ 转移,否则由于根必须被选,$i$ 不选,整棵子树都不能选,所以只能从 $r_i+1$ 转移过来。于是这样的复杂度就是 $O(nv)$ 的了。

暴力做是 $O(n^2v)$ 的,复杂度瓶颈在于枚举根。考虑一个性质,就是如果点 $v$ 不在答案中,那么与其相邻的连通块不会互相通达,因为树上路径唯一。于是就可以考虑点分,经过/不经过根分别对应分治下去和跨过分治中心两种情况。最终复杂度 $nv\log n$ 。

在合并的时候可能有亿点细节需要去写…233

点分树

引入

对于点分树,有一个很优秀的性质,就是树高不超过 $\log n$ ,对于一些题目可以用这个性质进行转化。

给定一棵无权树,单点修改,求距离 $x$ 不超过 $r$ 的点权和。

考虑如果没有修改操作时,直接求也是不太好求的。于是考虑点分治,对于每个分治中心,预处理记录一下子树中距离 $\leq k\quad (k=1,2,3\cdots )$ 的点权和。 注意到这最多需要 $n \log n$ 的空间,拿 vector 实现即可。

那么对于询问而言,直接从点分树上暴跳,每跳到一个点分中心 $p$,就可以加上这个点记录的 $\leq r-(dep_p-dep_x)$ 的点权和,并且减去上一个点分中心子树内部 $\leq r-(dep_p-dep_x)$ 的点权和。由于点分树树高的限制,这个过程是 $\log n$ 的。

考虑如何修改,发现本质上修改+询问是一个单点修改,前缀查询的过程,于是就可以换用树状数组来维护,修改时只需要暴力跳即可,这样最终复杂度就是 $m\log ^2 n$ 的了。

树上背包问题2

给定一棵树,树上每个点有一个权值一个重量。要求选择一个独立集,使得重量和小于某个给定的 $V$ 且权值和最大。

$n\leq 100,V\leq 30000$

考虑一个比较 general 的 $dp$ ,还是跟上个题一样,直接合并背包是 $V^2$ 的,所以考虑把这棵树的 $dfs$ 序写下来,然后 $f_{i,j,s}$ 表示考虑了前 $i$ 个点,容量为 $j$ ,每个点选不选表示为集合 $s$ ,最终复杂度就是 $nv2^n$ 。

考虑如何少记一点东西,似乎需要把这个 $2^n$ 给降下来。于是考虑点分治。发现点分治的每一层,子树之间都是互不影响的,所以只需要把点分树找出来,对点分树进行树形 $dp$ ,记 $s$ 时只需要记每一层的点分中心的状态即可。这样由于点分树高是 $O(\log n)$ 的,所以最终复杂度是 $O(nv2^{\log n})=O(n^2v)$ 。

ZJOI 2007 捉迷藏

修改⼀个点的⿊白,求最远⿊点之间距离。

考虑大致思路和「引入」中差不多,但是需要注意的是由于是统计最长的点对间距离,所以用边分治会好做一些。那么分治的时候还是需要按是否经过分治中心来分类。之后拿一个 multiset 来维护就好了。

嗯,除了边分不会写之外,没啥可说的。

据说还有 $1$ 个 $\log $ 的做法,那必然是鸽了。

补充题目

某不知名CF题

给一棵树,点、边均有权,求点 $x$,最小化 $\sum_{i=1}^{n} a_{i} \cdot \operatorname{dis}^{1.5}(i, x)$ 。 $n \leq 10^{5}$ 。

事实上是 CF566C (雾

首先对于 $1.5$ 次方的 $\sum $,由于相加之后二阶导依旧 $>0$ ,所以相加之后依旧是凸函数。那么也就是说,假设 $x$ 可以在边上随便取,那么对于一条固定的路径 $x\in(u,v)$ , $\mathrm{dis}(x,u)^{1.5}$ 必定是一个下凸函数。

考虑在链上必然是二分,那么调整到树上就可以进行点分。考虑对于每个点分中心,都应该找可以使答案变小的那个儿子所在子树点作为下一个进行点分的连通块。考虑如何去实现判断这个过程。如果答案变小,那么一定是导数减小,于是可以求出子树中每个点对应值的导数 $df_x$,那么总体的导数就是 $\sum df_x-2\cdot df_v<0$ ,$v$ 是下一个要进行点分的子树,原因是通过计算偏移量,剩余的点的 $f$ 都会变大,当前点会变小。这个求导的过程本质上是在模拟,我向每条边移动一个 $\epsilon$ 之后的结果。

于是就点分进行这个过程即可,点分是为了加速计算每个子树的 $df$ ,保证最终这一部分的计算量是 $n\log n$ 的。

可达性统计

给定一个有向图,每次加入一条边 $(u,v)$,或者询问有多少点对两两可达。

考虑一个深刻的单调性,如果在某一时刻出现了一个SCC,把它缩起来,那么之后它也会一直被缩起来。

于是考虑整体二分,solve(l,r,E) 表示 $E$ 中的边会在时刻 $l\sim r$ 中被缩起来。于是每次把 $[l,mid]$ 这些边跑一个强连通分量,那么被缩起来的边递归到 solve(l,mid,E1) 里面,没被缩起来的边递归到 solve(mid+1,r,E2) 里面。同时为了让分治的复杂度是对的,每次点集大小不能跟 $n$ 有关,于是就需要每次在 solve(l,mid,E1) 之后把 E1里的点拿并查集给缩起来,这样才能保证 solve(mid+1,r,E2) 的复杂度只跟边数有关。

总结

动态点分治是不可能的,这辈子都不可能的。