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)$ 的三元组，使得 $u,v,w$ 都不相同，并存在两条路径：$u$ 到 $w$ 之间和 $v$ 到 $w$ 之间，使得两条路径没有共同边。

题目描述

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.

输入输出格式

输入格式

First line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ), 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<=10^{5} $ ), 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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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.