树分治学习笔记

点分治

0.用处

点分治一般用于树上路径的问题。

比如求条数等。

1.点分治过程

1. 选择一个根节点

2. 计算贡献，贡献一般有一下两种

1.两个点的路径经过根节点
2.两个点在同一个子树内

3. 然后把根节点删掉，分成若干棵树，对每一棵树做同样的操作

然后每一次我们只需要计算两个点的路径经过根节点的贡献即可。

2.例题

例题1

首先我们先想暴力，的写法。我们枚举点 \(u\)，为点 \(u\) 是首都的答案。

然后我们把所有和 \(u\) 相连的所有城市加入队列里，然后我们遍历队列里的点。

假如队列里的点的父亲是其他城市的，那么就把这个城市的所有点加进来。

假如队列里的父亲已经入队过，忽略最后我们统计有多少种点入过队，那么就是答案。

时间复杂度为 \(n^2\)。

然后我们考虑优化。

如果以 \(u\) 为根节点的答案不会劣于其他为根节点选 \(u\) 的答案。

那么我可以直接把以 \(u\) 为根的方案替换成以其它点为根时选了 \(u\) 的方案。

也就是说，以一个点 \(u\) 为根求完答案的时候，求 \(u\) 的子树内的点的答案时，就不会再把 \(u\) 加进它们的方案，也就是不会再经过 \(u\)，去选其他子树点。

于是点分治即可。时间复杂度为 \(n \log n\)。

代码后面放。