ROI 2015 Day1 珍珠刺绣

因为原先的图是一棵树，显然每次询问的子图都是森林。

森林连通块数量启发我们使用 $V - E$ 计算。

把边分成横向的和纵向的两部分，然后我们需要维护：一个子矩形内点数量，横向边数量，纵向边数量。

边数量显然是可以把每个边的贡献算到其中一个端点上进行维护的，这里不妨将 $(x, y)$ 和 $(x, y + 1)$ 的边的贡献放到 $(x, y)$ 上，$(x, y)$ 和 $(x + 1, y)$ 的边同理贡献放到 $(x, y)$ 上，则横向边数量为 $(x_1 , y_1 )$ 到 $(x_2 , y_2 − 1)$ 的贡献和，纵向边同理，数量为 $(x_1 , y_1 )$ 到 $(x_2 − 1, y_2 )$ 的贡献和。

注意到点数和边数是 $O(n)$ 的，因此可以离线之后用扫描线和树状数组维护。

感觉思路上和 APIO2017 斑斓之地 类似。