一些树上问题的小技巧

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

树上差分

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

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

练习题目

• P3128 [USACO15DEC]Max Flow P

• P3258 [JLOI2014]松鼠的新家

• P8201 生活在树上（hard version）

• P1600 [NOIP2016 提高组] 天天爱跑步

两条路径的交

有个结论：若树上两条路径 $a\to b$ 和 $c\to d$ 有交，那么令 $\operatorname{lca}(a,b)=x,\operatorname{lca}(c,d)=y$，要么 $x$ 在 $c\to d$ 上，要么 $y$ 在 $a\to b$ 上。

证明如下：

把 $a,b,x$ 画出来：（写文章时图论编辑器上不去……）

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

还有一种可能就是 $c\to d$ 在 $x$ 的子树内，不难发现此时的情况相当于把 $a\to b$ 和 $c\to d$ 这两条路径交换。

综上，得证。

练习题目

• P3398 仓鼠找 sugar

点边容斥

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

例题：

给定一个 $n$ 个点的无向图，点 $i$ 和 点 $j$ 之间有 $c_{i,j}$ 条互不相同的边。

计算满足以下所有条件的生成树的数量，模 $998244353$：

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

$1\le n\le 500$。