P17268 [ICPC 2017 Urumqi R] Lowest Common

在图论中，有根树 $T$ 中两个节点 $v$ 和 $w$ 的 **最近公共祖先 (LCA)** 是以 $v$ 和 $w$ 为后代的最深节点。此处我们定义每个节点是自身的后代。$T$ 中两个节点的 LCA 是它们离根最远的公共祖先。 但是，如果是一棵无根树呢？ 在本题中，你得到一棵具有 $n$ 个节点（编号从 $1$ 到 $n$）的无根树 $T$，以及若干对节点 $(v_i, w_i)$。 对于 $T$ 的每个节点 $x$，考虑以 $x$ 为根得到的树（成为一棵有根树）；计算求和 $\sum_{i} LCA(v_i, w_i)$。

输入包含多组测试数据，第一行包含一个整数 $t$ ($1 \le t \le 28$)，表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100000$)。接下来的 $n - 1$ 行，每行包含两个整数 $v$ 和 $w$ ($1 \le v, w \le n$)，描述一条边。随后的 $q$ 行包含 $q$ 对节点 $(v_i, w_i)$，描述如上 ($1 \le v_i, w_i \le n$)。 输入中所有 $n$ 的总和与所有 $q$ 的总和均小于 $1000000$。

对于每组测试数据，输出一行 $n$ 个整数。 第 $i$ 个整数对应以第 $i$ 个节点为根时 $\sum_{i} LCA(v_i, w_i)$ 的值。

翻译由 DeepSeek V4 Pro 完成