Path Triples On Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is given a tree of N nodes. Let M denote the number of simple paths with at least two nodes. Notice that M = N * (N  1) / 2.
There are (M * (M  1) * (M  2) / 6) unordered triples of such paths. Your task is to count how many of them are nice. A triple of paths (A, B, C) is nice if and only if either of the following conditions is satisfied:
 The three paths are pairwise disjoint (no two of them share a node).
 Each pair of paths intersect with each other. In other words: paths A and B share at least one node, paths A and C share at least one node, and also paths B and C share at least one node.
Output the number of nice triples of paths modulo (10^{9}+7).
Input
The first line of the input contains an integer N.
Each of the next N1 lines contains two integers a_{i} and b_{i} denoting an edge between nodes a_{i} and b_{i}.
Output
Output a single integer, denoting the number of nice triples of paths modulo (10^{9}+7).
Constraints
 1 ≤ N ≤ 3*10^{5}
 1 ≤ a_{i}, b_{i} ≤ N
 a_{i} ≠ b_{i}
Subtasks
Subtask 1 (15 points): 1 ≤ N ≤ 2000
Subtask 2 (57 points):
 1 ≤ N ≤ 10^{5}
Subtask 3 (28 points):
 Original constraints.
Example
Input 1: 4 1 2 2 3 3 4 Output 1: 16 Input 2: 13 1 2 1 3 1 4 2 5 2 6 3 7 4 8 7 9 9 10 10 11 11 12 12 13 Output 2: 43484
Explanation
Example test 1. Let (x, y) denote the simple path between nodes x and y. There are 16 nice triples of paths: (1, 2), (1, 3), (1, 4)
 (1, 2), (1, 3), (2, 3)
 (1, 2), (1, 3), (2, 4)
 (1, 2), (1, 4), (2, 3)
 (1, 2), (1, 4), (2, 4)
 (1, 2), (2, 3), (2, 4)
 (1, 3), (1, 4), (2, 3)
 (1, 3), (1, 4), (2, 4)
 (1, 3), (1, 4), (3, 4)
 (1, 3), (2, 3), (2, 4)
 (1, 3), (2, 3), (3, 4)
 (1, 3), (2, 4), (3, 4)
 (1, 4), (2, 3), (2, 4)
 (1, 4), (2, 3), (3, 4)
 (1, 4), (2, 4), (3, 4)
 (2, 3), (2, 4), (3, 4)
Example test 2. The triple {(1, 5), (3, 7), (9, 13)} is one of the 43484 nice triples of paths.
Author:  r_64 
Tester:  xcwgf666 
Editorial  https://discuss.codechef.com/problems/TUPLES2 
Tags  centroiddecomp, dynamicprogramming, hard, march17, r_64, tree 
Date Added:  7022017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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 
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. 