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/A

N/A

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.