CF855G Harry Vs Voldemort

在摧毁了所有伏地魔的魂器后，哈利与伏地魔迎来了最终决战。他们各自用魔杖释放咒语，咒语在空中相撞。 决斗地点是霍格沃茨，可以用一棵树来表示。霍格沃茨共有 $n$ 个地点，通过 $n-1$ 条无向道路连接。 作为旁观者的罗恩，对这场决战产生了好奇。他想知道有多少个地点三元组 $(u, v, w)$ 满足如下条件：如果哈利站在 $u$ 处、伏地魔站在 $v$ 处，则他们的咒语会在 $w$ 处相撞。对于一个三元组，只有当 $u$、$v$、$w$ 均不相同，并且存在从 $u$ 到 $w$ 和从 $v$ 到 $w$ 的两条路径，这两条路径不经过相同的道路时，才满足要求。 同时，由于激烈的战斗，不断有新的道路被修建。每修建一条新路，你都需要告诉罗恩当前满足条件的三元组数。 形式化地说，给定一个 $n$ 个点、$n-1$ 条边构成的树。接下来会有 $q$ 个新边被加入树的某两节点之间。每次加边后，你都要输出当前满足题意的三元组 $(u, v, w)$ 个数。

第一行，一个整数 $n$（$1 \leq n \leq 10^{5}$），表示霍格沃茨的地点数。 接下来的 $n-1$ 行，每行两个用空格分隔的整数 $u$ 和 $v$（$1 \leq u,v \leq n$），表示这两个地点之间有一条道路。保证这些道路形成一棵连通无环的树。 接下来一行，一个整数 $q$（$1 \leq q \leq 10^{5}$），表示将要加入的新道路数量。 接下来的 $q$ 行，每行两个用空格分隔的整数 $u$ 和 $v$（$1 \leq u,v \leq n$），表示将在 $u$ 和 $v$ 之间新增加一条道路。 注意：新边可能会连接已存在边的节点对，也可能连接同一个节点自身。

第一行输出原始树中满足条件的三元组个数。 接下来 $q$ 行，每行输出当前加入第 $i$ 条新边后满足条件的三元组个数 $ans_i$。

在第一个样例中，原始树只有 $(1,3,2)$ 和 $(3,1,2)$ 这两个满足条件的三元组。 在加入 $2$ 到 $3$ 的边后，满足条件的三元组为 $(1,3,2)$、$(3,1,2)$、$(1,2,3)$ 和 $(2,1,3)$。 由 ChatGPT 5 翻译