T3 枢纽（junction）

我们先给一个图。

由图可知有 $(1,8),(1,9),(1,10),(2,8),(2,9),(2,10),(3,8),(3,9),(3,10)$ 这几对点满足题意要求。

通过观察可以发现 $a$ 与 $b$ 之间的节点所通向的路径，无论是通向 $a$ 的左边，还是通向 $b$ 的右边，都不会包含 $a$ 或 $b$。

假设以节点序号较小为起点，较大为终点，我们可以得到：以 $a$ 左边的节点为起点，以 $b$ 右边的节点为终点，所构成的路径一定包含 $a$ 与 $b$。

显然，一个节点把图分为两边，那么图的左边除了经过该节点，没有可以不经过该节点而到达图的右边的路径。也就是，这个节点无可避免地经过 $a$ 和 $b$，无法绕路。而最后 $(u,v)$ 的数量，就是 $a$ 左边的节点数量 $\times$ $b$ 右边的节点数量。

考虑搜索。我们先假定起点为 $a$，终点为 $b$。从 $a$ 出发开始搜，到 $b$ 为止，没有搜到的点就是 $b$ 右边的点。（参见下图）

黄线为以 $a$ 为起点会搜到的路径，只要给搜到的点打上标记，就可以知道 $b$ 右边点的数量。同理，我们以 $b$ 为起点，也可以搜出 $a$ 左边的点。两边的答案相乘，就可以得到题目的答案。

那么如何实现呢？

• 设一个记录访问的数组 $fl$。

• 给终点（$a$ 或 $b$）先打上标记，搜到那里时就停。

• 只要碰到没有搜过的，就继续搜下去。因为终点已经打上标记的，而且是联通图，所以没搜到的点就一定是 $a$ 左边或 $b$ 右边。

这样，我们很容易使用 bfs 或 dfs 解决此题。