← 返回题目列表

Codeforces · 855/G

G. 哈利与伏地魔

中文机器翻译题面 查看原题

在摧毁伏地魔的所有魂器后,哈利和伏地魔准备进行最后的战斗。他们各自用魔杖施展咒语,咒语发生碰撞。

战斗场景是霍格沃茨,可以用树的形式来表示。霍格沃茨总共有 n 个地方使用 n - 1 条无向道路相连。

罗恩正在观看哈利和伏地魔之间的这场战斗,他想知道有多少个三元组(u,v,w),这样如果哈利站在u位置而伏地魔站在v位置,他们的咒语会在w位置发生碰撞。仅当 u、v 和 w 不同,并且存在从 u 到 w 和从 v 到 w 的路径不经过相同的道路时,这对于三元组才是可能的。

现在,由于战斗的破坏,新的路径一直在添加。每次添加后你必须告诉罗恩答案。

正式地,你会得到一棵有 n 个顶点和 n - 1 条边的树。 q 在树的节点之间添加新的边。每次相加后,您需要告诉三元组 (u, v, w) 的数量,使得 u、v 和 w 不同,并且存在两条路径,一条在 u 和 w 之间,另一条在 v 和 w 之间,这样这些路径没有公共边。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105),即霍格沃茨的名额。

接下来的 n - 1 行中的每一行都包含两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n),指示位置 u 和 v 之间的道路。保证给定的道路形成连通树。

下一行包含一个整数 q (1 ≤ q ≤ 105),即添加的新边的数量。

接下来的 q 行包含两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n),表示要添加的新道路。

请注意,新添加的道路有可能连接之前由道路连接的地点。此外,一条新添加的道路可能会将一个地方与其自身连接起来。

输出

在第一行中打印发生任何更改之前的三元组数量的值。

之后打印 q 行,每行中包含一个整数 ansi,其中包含第 i 条边相加后的三元组数量的值。

示例

输入 #1

3
1 2
2 3
1
2 3

输出 #1

2
4

输入 #2

4
1 2
2 3
2 4
2
1 4
3 4

输出 #2

6
18
24

输入 #3

5
1 2
2 3
3 4
4 5
1
1 5

输出 #3

20
60

注意

在第一个示例中,对于初始树,我们将 (1, 3, 2) 和 (3, 1, 2) 作为唯一可能的三元组 (u, v, w)。

将 2 到 3 的边相加后,我们有 (1, 3, 2)、(3, 1, 2)、(1, 2, 3) 和 (2, 1, 3) 作为可能的三元组。