这篇学习笔记整理了一些小技巧。
树上差分
假设要让 a→b 的路径上的点都加上一个权值,那么可以通过维护每个节点到根的权值和 si,每次询问就在 sa 和 sb 都加上权值,slca(a,b) 和 sfa(lca(a,b)) 减掉权值,最后 dfs 计算一遍即可。
这个技巧有诸多变形,可以通过练习题深入学习。
练习题目
两条路径的交
有个结论:若树上两条路径 a→b 和 c→d 有交,那么令 lca(a,b)=x,lca(c,d)=y,要么 x 在 c→d 上,要么 y 在 a→b 上。
证明如下:
把 a,b,x 画出来:(写文章时图论编辑器上不去……)
容易发现,x 把它的子树“堵住”了,想要进去就必须经过它。但 a→b 肯定在 x 的子树内,所以子树外面的链想和 a→b 相交就一定要经过 x。
还有一种可能就是 c→d 在 x 的子树内,不难发现此时的情况相当于把 a→b 和 c→d 这两条路径交换。
综上,得证。
练习题目
点边容斥
树上连通块满足 点数−边数=1。
例题:
给定一个 n 个点的无向图,点 i 和 点 j 之间有 ci,j 条互不相同的边。
计算满足以下所有条件的生成树的数量,模 998244353:
- 共有 K 个要求,每个要求给出一个节点子集 S,要求生成树在仅保留 S 中的点和它们之间的边时,S 的导出子图仍然连通;
1≤n≤500。
题解
点边容斥,限制相当于点集 S 内(两端点都在点集里)的树边数量 cnt 恰好为 ∣S∣−1。注意到有 cnt≤∣S∣−1,故给边 (x,y) 一个权值表示有多少个限制点集同时包含了 x 和 y,问题就转化为最大生成树计数,使用矩阵树定理即可。
注意要判无解。