主要思路
好题！好题！
这个题首先需要了解到一个性质：每个点所能到达的、进行贸易的国家的集合可以形成一个连通的生成子图。所以，我们最后需要求的就是每个国家对应的集合的大小。
如何去快速求这个东西呢？我们需要把 \(m\) 个路径中每个跨过当前点 \(u\) 的路径给拿出来，然后算这些路径的交集。这样是一种计算的方法，但是确实不快速。
Continue reading →好题！好题！
这个题首先需要了解到一个性质：每个点所能到达的、进行贸易的国家的集合可以形成一个连通的生成子图。所以，我们最后需要求的就是每个国家对应的集合的大小。
如何去快速求这个东西呢？我们需要把 \(m\) 个路径中每个跨过当前点 \(u\) 的路径给拿出来，然后算这些路径的交集。这样是一种计算的方法，但是确实不快速。
Continue reading →我们发现，其实这道题就是要求询问无向图上点对之间的割点数量：可以确定割点的数量是唯一的，因为如果有更多的割点，那么不存在更少的割点使点双连通分量连通。
既然我们知道了大概的题意和要求，那么我们可以发现：如果把这些割点所在域内的非割点全部缩成一个点，然后让割点分别连接，那么根据「不存在更少的割点使点双连通分量连通」的「唯一性」，可以知道这样建出来的东西一定是一棵树。
这样就很好做了！直接树上差分+LCA即可。我们需要用 Tarjan 把这些点缩起来，通过割点进行连接，然后做一遍 DFS 之类的获取前缀和，再处理 LCA 倍增数组，我们就可以在线回答询问了。算法的复杂度为\(\Theta(n \log n + m \log n)\)。
这道题可以离线回答，很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息，然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG，但是我们可以动态开点，然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的，这样空间就可以接受的了。
既然有了很好用的动态开点线段树，我们就可以用树上差分那一套路，在端点和\(LCA\)处打标记，然后考虑从下往上合并答案。合并可以用线段树合并，复杂度为重合部分，差不多就是\(O(\log n)\)。然后就没了，很傻逼的一道题。
学习树上差分的前提是：
学习了这些之后，我们就可以开始学习树上差分了。树上差分的思想跟差分类似：都是在不得不求前缀和的情况下，将区间操作变为单点操作，降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过，所以学习树上差分很有必要（我怀疑是出题组不敢出树链剖分，但又要考察选手们对树上操作的熟悉程度，所以采用了这么个坑爹玩意）。我们先来学习一个基本的操作：点的链上区间加。