
ZOJ Problem Set  4121
DreamGrid has just found a tree of $n$ vertices in his backyard. As DreamGrid loves connected components, he defines an interval $[l, r]$ ($1 \le l \le r \le n$) as a "connected interval" if the induced subgraph formed from the set $\mathbb{V} = \{v_i  i \in [l, r]\}$ consists of exactly one connected component, where $v_i$ indicates the vertex whose index is $i$. Given the tree in DreamGrid's backyard, your task is to help DreamGrid count the number of connected intervals. Recall that an induced subgraph $G'$ of a graph $G$ is another graph, formed from a subset $\mathbb{V}$ of the vertices of the graph $G$ and all of the edges in graph $G$ connecting pairs of vertices in $\mathbb{V}$. InputThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 3 \times 10^5$) indicating the size of the tree. For the following $(n1)$ lines, the $i$th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) indicating that there is an edge connecting vertex $a_i$ and vertex $b_i$ in the tree. It's guaranteed that the given graph is a tree and that the sum of $n$ in all test cases will not exceed $3 \times 10^5$. OutputFor each test case output one line containing one integer, indicating the number of connected intervals. Sample Input2 4 1 2 2 3 3 4 4 1 2 2 3 2 4 Sample Output10 9 HintFor the first sample test case, all intervals are connected intervals. For the second sample test case, all intervals but [3, 4] are connected intervals. Author: LIN, Xi Source: The 10th Shandong Provincial Collegiate Programming Contest 