CF855G.Harry Vs Voldemort

After destroying all of Voldemort's Horcruxes, Harry and Voldemort are up for the final battle. They each cast spells from their wands and the spells collide.

The battle scene is Hogwarts, which can be represented in the form of a tree. There are, in total, n places in Hogwarts joined using n - 1 undirected roads.

Ron, who was viewing this battle between Harry and Voldemort, wondered how many triplets of places (u, v, w) are there such that if Harry is standing at place u and Voldemort is standing at place v, their spells collide at a place w. This is possible for a triplet only when u, v and w are distinct, and there exist paths from u to w and from v to w which do not pass through the same roads.

Now, due to the battle havoc, new paths are being added all the time. You have to tell Ron the answer after each addition.

Formally, you are given a tree with n vertices and n - 1 edges. q new edges are being added between the nodes of the tree. After each addition you need to tell the number of triplets (u, v, w) such that u, v and w are distinct and there exist two paths, one between u and w, another between v and w such that these paths do not have an edge in common.

在摧毁伏地魔的所有魂器后，哈利与伏地魔迎来了最终决战。他们各自从魔杖中施放咒语，两道咒语发生碰撞。

决战场景霍格沃茨可建模为一棵树。霍格沃茨共有 $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$ 的路径，使得这两条路径没有公共边。

First line contains an integer n (1 ≤ n ≤ 105), the number of places in Hogwarts.

Each of the next n - 1 lines contains two space separated integers u and v (1 ≤ u, v ≤ n) indicating a road between places u and v. It is guaranteed that the given roads form a connected tree.

Next line contains a single integer q (1 ≤ q ≤ 105), the number of new edges being added.

Each of the next q lines contains two space separated integers u and v (1 ≤ u, v ≤ n) representing the new road being added.

Note that it is possible that a newly added road connects places that were connected by a road before. Also, a newly added road may connect a place to itself.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示霍格沃茨中地点的数量。

接下来的 $n-1$ 行，每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示地点 $u$ 与地点 $v$ 之间有一条道路。保证所给的道路构成一棵连通树。

下一行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示将要添加的新边的数量。

接下来的 $q$ 行，每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示将要添加的一条新道路。

注意：新添加的道路可能连接原本已由一条道路直接连通的两个地点；此外，新添加的道路也可能连接一个地点到其自身。

In the first line print the value for the number of triplets before any changes occurred.

After that print q lines, a single integer ans__i in each line containing the value for the number of triplets after i-th edge addition.

第一行输出在任何更改发生前的三元组数量。

随后输出 q 行，每行一个整数 ans__i，表示第 i 次添加边之后的三元组数量。

In the first sample case, for the initial tree, we have (1, 3, 2) and (3, 1, 2) as the only possible triplets (u, v, w).

After addition of edge from 2 to 3, we have (1, 3, 2), (3, 1, 2), (1, 2, 3) and (2, 1, 3) as the possible triplets.

在第一个样例中，对于初始树，唯一可能的三元组 $(u,\,v,\,w)$ 是 $(1,\,3,\,2)$ 和 $(3,\,1,\,2)$。

在添加从节点 $2$ 到节点 $3$ 的边后，可能的三元组变为 $(1,\,3,\,2)$、$(3,\,1,\,2)$、$(1,\,2,\,3)$ 和 $(2,\,1,\,3)$。