CF1486F Pairs of Paths

给定一棵包含 $n$ 个顶点的树，以及 $m$ 条简单顶点路径。你的任务是计算有多少对路径恰好在一个顶点处相交。更正式地，你需要找出有多少对 $(i, j)$（$1 \leq i < j \leq m$），使得 $path_i$ 和 $path_j$ 恰好有一个公共顶点。

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）。 接下来的 $n-1$ 行描述这棵树。每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示在顶点 $u$ 和顶点 $v$ 之间有一条边。 下一行包含一个整数 $m$（$1 \leq m \leq 3 \cdot 10^5$）。 接下来的 $m$ 行描述路径。每行通过其两个端点 $u$ 和 $v$（$1 \leq u, v \leq n$）描述一条路径。给定的路径是从 $u$ 到 $v$ 的最短路径上的所有顶点（包括 $u$ 和 $v$）。

输出一个整数，表示有多少对路径恰好在一个顶点处相交。

 第一组样例中的树和路径如上图所示。路径对 $(1,4)$ 和 $(3,4)$ 恰好在一个顶点处相交。 在第二组样例中，三条路径都只包含同一个顶点，因此所有路径对 $(1,2)$、$(1,3)$ 和 $(2,3)$ 都恰好在一个顶点处相交。 第三组样例与第一组相同，但多了两条路径。路径对 $(1,4)$、$(1,5)$、$(2,5)$、$(3,4)$、$(3,5)$、$(3,6)$ 和 $(5,6)$ 恰好在一个顶点处相交。 由 ChatGPT 4.1 翻译