Tree Connectivity

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef recently got influenced by the Joker and loves to carve things up with his new collection of knives.
One afternoon Chef decides to cut off some vertices from a tree that has N vertices. Chef creates the following plan for cutting the vertices :
 He chooses a pair of integers (L, R) such that (1≤L≤R≤N) and cuts off all vertices whose indices do not belong in the interval [L, R].
 He also cuts off all edges that don’t connect any two vertices belonging to the interval [L, R].
A pair of integers [L, R] is said to be valid if the remaining graph after cutting the vertices according to Chef's plan is still connected.
The Chef wants to know the number of such valid pairs (L, R) for his tree. However, duty calls for the Chef and he has to rush back to the kitchen to cook. Can you help him to calculate the number of such valid pairs?
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The description of each test case starts with the number of vertices N. Each of the following N  1 lines contains two integers  indices of vertices connected by an edge. It is guaranteed that each test case defines a valid tree.
Output
For each test case, output a single line containing the number Chef is interested in.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ N ≤ 10^{6}
 The sum of N over all testcases does not exceed 10^{6}
Example
Input: 2 2 2 1 4 3 4 1 4 4 2 Output: 3 7
Explanation
Example case 1. Intervals [1,1], [1,2] and [2,2] are valid.
Example case 2. Intervals [1,1], [1,4], [2,2], [2,4], [3,3], [3,4] and [4,4] are valid.
Author:  melnik 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/TRCNTCT 
Tags  cook85, dfs, divideandconq, hard, melnik, segmenttree 
Date Added:  16082017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 