All submissions for this problem are available.
Each member of the Justice League is assigned a code number, which they use, along with the DNA test, to teleport into the the Watchtower, so that shapeshifters and telepaths cannot defile the sancity of the Watchtower. For example, Superman is 1 and Batman is 2. Each new member is inducted by an older member (Please note that the newer member may have a code number greater than the older member's code number). For each member, the Leaguer who inducted them share a mutual special bond with them. The special bonds form a tree with nodes representing the team members, each node being labelled by the code number of the member. The evil Lex Luthor studies this tree to find the weaknesses of the team. He finds that the weakness coefficient of the team is the number of paths in the tree such that it contains all the nodes between l and r (l<=r) and no other nodes. For all his blabbering about being a genius, he has kidnapped you to help him do that. Solve the problem to save yourself.
The first line contains the number of test cases, t.
- For each test case, the first line contains the number of members, n.
- Don't write any constraints here, use section "Constraints" for this below.
- The next (n-1) lines contain 2 integers, x and y denoting that they share a special bond.
For each test case, print the weakness coefficient of the team.
- n ≤ 1e5
- Summation of n over all test cases <= 1e5+1000
Input: 1 3 1 2 2 3 Output: 6
Example case 1.: There are 6 such paths- (1,1),(2,2),(3,3),(1,2),(2,3),(1,2,3)
|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, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions