一些树上问题的小技巧

这篇学习笔记整理了一些小技巧。

树上差分

假设要让 aba\to b 的路径上的点都加上一个权值,那么可以通过维护每个节点到根的权值和 sis_i,每次询问就在 sas_asbs_b 都加上权值,slca(a,b)s_{\operatorname{lca}(a,b)}sfa(lca(a,b))s_{\operatorname{fa}(\operatorname{lca}(a,b))} 减掉权值,最后 dfs 计算一遍即可。

这个技巧有诸多变形,可以通过练习题深入学习。

练习题目

两条路径的交

有个结论:若树上两条路径 aba\to bcdc\to d 有交,那么令 lca(a,b)=x,lca(c,d)=y\operatorname{lca}(a,b)=x,\operatorname{lca}(c,d)=y,要么 xxcdc\to d 上,要么 yyaba\to b


证明如下:

a,b,xa,b,x 画出来:(写文章时图论编辑器上不去……)

容易发现,xx 把它的子树“堵住”了,想要进去就必须经过它。但 aba\to b 肯定在 xx 的子树内,所以子树外面的链想和 aba\to b 相交就一定要经过 xx

还有一种可能就是 cdc\to dxx 的子树内,不难发现此时的情况相当于把 aba\to bcdc\to d 这两条路径交换

综上,得证。


练习题目

点边容斥

树上连通块满足 点数边数=1\text{点数}-\text{边数}=1

例题:

给定一个 nn 个点的无向图,点 ii 和 点 jj 之间有 ci,jc_{i,j} 条互不相同的边。

计算满足以下所有条件的生成树的数量,模 998244353998244353

  1. 共有 KK 个要求,每个要求给出一个节点子集 SS,要求生成树在仅保留 SS 中的点和它们之间的边时,SS 的导出子图仍然连通;

1n5001\le n\le 500

题解

点边容斥,限制相当于点集 SS 内(两端点都在点集里)的树边数量 cntcnt 恰好为 S1|S|-1。注意到有 cntS1cnt\le |S|-1,故给边 (x,y)(x,y) 一个权值表示有多少个限制点集同时包含了 xxyy,问题就转化为最大生成树计数,使用矩阵树定理即可。

注意要判无解。