Harry Vs Voldemort
Contest: Manthan, Codefest 17
Difficulty rating: 3300
Tags: dfs and similar, dp, graphs, trees

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.

Input format:
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.

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

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
1 2
2 3
1
2 3

Example output:
2
4

Example input:
4
1 2
2 3
2 4
2
1 4
3 4

Example output:
6
18
24

Editorial:
• At first let's solve the problem for the initial tree. You can use dynamic programming.
• The second part of the problem was to realize that we need to count the triple (u, v, w) if and only if the following condition holds: w is in a edge-2-connectivity component that is on the path from the edge-2-connectivity component of u and the edge-2-connectivity of v.
• When an edge is added, it compresses all edge-2-connectivity components on the path between its ends. We can list all these components and then merge them in O(number of the components) time, because once we list all these components, they disappear. In other words, each component is listed at most once through the entire process, and the total number of components is O(n).
• How do we recalculate the answer given the components we need to merge into a single one? It can be done directly considering all cases of which of u, v and w are in this new component. The only tough idea may be that you need to, for each component, keep the number of pairs (u, v) such that u and v are not in this component, and edges (bridges) towards u and v from this component are different.
• For more details about case-work see the code below.