P14050 [SDCPC 2019] Connected Intervals

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}$.

There 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 $(n-1)$ 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$.

For each test case output one line containing one integer, indicating the number of connected intervals.

For the first sample test case, all intervals are connected intervals. For the second sample test case, all intervals but $[3, 4]$ are connected intervals.