English · Original
Chinese · Translation
Formal · Original
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
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
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.
[samples]
## 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.
在摧毁了伏地魔的所有魂器后，哈利与伏地魔迎来了最终对决。他们各自从魔杖中施放咒语，咒语在空中相撞。
这场战斗的场景是霍格沃茨，可以用一棵树来表示。霍格沃茨共有 #cf_span[n] 个地点，通过 #cf_span[n - 1] 条无向道路连接。
罗恩正在观看哈利与伏地魔的战斗，他想知道有多少个三元组地点 #cf_span[(u, v, w)] 满足：当哈利站在地点 #cf_span[u]、伏地魔站在地点 #cf_span[v] 时，他们的咒语在地点 #cf_span[w] 相撞。只有当 #cf_span[u]、#cf_span[v] 和 #cf_span[w] 互不相同，且存在从 #cf_span[u] 到 #cf_span[w] 和从 #cf_span[v] 到 #cf_span[w] 的两条路径，且这两条路径不经过相同的道路时，该三元组才成立。
由于战斗混乱，新的路径正不断被添加。你需要在每次添加后告诉罗恩答案。
形式化地说，你被给定一棵包含 #cf_span[n] 个顶点和 #cf_span[n - 1] 条边的树。随后将添加 #cf_span[q] 条连接树中节点的新边。每次添加后，你需要计算满足以下条件的三元组 #cf_span[(u, v, w)] 的数量：#cf_span[u]、#cf_span[v] 和 #cf_span[w] 互不相同，且存在两条路径——一条连接 #cf_span[u] 与 #cf_span[w]，另一条连接 #cf_span[v] 与 #cf_span[w]——这两条路径没有公共边。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示霍格沃茨的地点数量。
接下来的 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n])，表示地点 #cf_span[u] 与 #cf_span[v] 之间有一条道路。保证给出的道路构成一棵连通树。
下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示将要添加的新边数量。
接下来的 #cf_span[q] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n])，表示将要添加的新道路。
注意，新添加的道路可能连接原本已由道路相连的地点，也可能连接一个地点到其自身。
第一行输出在任何更改发生前的三元组数量。
随后输出 #cf_span[q] 行，每行一个整数 #cf_span[ansi]，表示在第 #cf_span[i] 条边添加后的三元组数量。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示霍格沃茨的地点数量。接下来的 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n])，表示地点 #cf_span[u] 与 #cf_span[v] 之间有一条道路。保证给出的道路构成一棵连通树。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示将要添加的新边数量。接下来的 #cf_span[q] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n])，表示将要添加的新道路。注意，新添加的道路可能连接原本已由道路相连的地点，也可能连接一个地点到其自身。
## Output
第一行输出在任何更改发生前的三元组数量。随后输出 #cf_span[q] 行，每行一个整数 #cf_span[ansi]，表示在第 #cf_span[i] 条边添加后的三元组数量。
[samples]
## Note
在第一个样例中，初始树上仅有两个可能的三元组 #cf_span[(1, 3, 2)] 和 #cf_span[(3, 1, 2)]。在添加从 #cf_span[2] 到 #cf_span[3] 的边后，可能的三元组变为 #cf_span[(1, 3, 2)]、#cf_span[(3, 1, 2)]、#cf_span[(1, 2, 3)] 和 #cf_span[(2, 1, 3)]。
**Definitions**
Let $G = (V, E)$ be an undirected multigraph where $V$ is the set of vertices and $E$ is the multiset of edges.
Let $\Pi(x, y; G)$ denote the set of all simple paths between vertices $x$ and $y$ in $G$.
For a path $\pi$, let $E(\pi)$ denote the set of edges in that path.
Define the set of valid triplets $\mathcal{T}(G)$ as:
$$
\mathcal{T}(G) = \left\{ (u, v, w) \in V^3 \ \middle|\
\begin{aligned}
& 1.\ u \neq v, u \neq w, v \neq w \\
& 2.\ \exists \pi_1 \in \Pi(u, w; G), \exists \pi_2 \in \Pi(v, w; G) \text{ such that } E(\pi_1) \cap E(\pi_2) = \emptyset
\end{aligned}
\right\}
$$
**Input Data**
1. An integer $n$ ($1 \le n \le 10^5$).
2. A set of edges $E_{init} = \{(u_i, v_i)\}_{i=1}^{n-1}$ such that the graph $G_0 = (V, E_{init})$ is a connected tree, where $V = \{1, \dots, n\}$.
3. An integer $q$ ($1 \le q \le 10^5$).
4. A sequence of edge additions $A = \langle (x_1, y_1), (x_2, y_2), \dots, (x_q, y_q) \rangle$, where $1 \le x_j, y_j \le n$. Note that $G$ may contain self-loops and multiple edges.
**Problem Statement**
Let $G_0 = (V, E_{init})$.
For $k = 1, \dots, q$, let $G_k = (V, E_k)$ where $E_k = E_{k-1} \cup \{(x_k, y_k)\}$.
**Objective**
Compute and output the sequence of integers $ans_0, ans_1, \dots, ans_q$, defined as:
$$ ans_k = |\mathcal{T}(G_k)| $$
for $k = 0, 1, \dots, q$.
API Response (JSON)
{
"problem": {
"name": "G. Harry Vs Voldemort",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF855G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nThe battle scene is Hogwarts, which can ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在摧毁了伏地魔的所有魂器后，哈利与伏地魔迎来了最终对决。他们各自从魔杖中施放咒语，咒语在空中相撞。\n\n这场战斗的场景是霍格沃茨，可以用一棵树来表示。霍格沃茨共有 #cf_span[n] 个地点，通过 #cf_span[n - 1] 条无向道路连接。\n\n罗恩正在观看哈利与伏地魔的战斗，他想知道有多少个三元组地点 #cf_span[(u, v, w)] 满足：当哈利站在地点 #cf_span[u]、伏...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions**\n\nLet $G = (V, E)$ be an undirected multigraph where $V$ is the set of vertices and $E$ is the multiset of edges.\nLet $\\Pi(x, y; G)$ denote the set of all simple paths between vertices ...",
"is_translate": false,
"language": "Formal"
}
]
}