All submissions for this problem are available.Chef lives in Treeland which, as the name implies, is shaped like a [tree](https://en.wikipedia.org/wiki/Tree_(data_structure)). Chef's home, his school, and the playground where he likes to play are located on three different vertices in this tree. Chef tells you that every morning he walks across $x$ edges on the simple path from his home to his school. In the afternoon, he walks along the simple path from his school to the playground crossing $y$ edges. And in the evening, he walks back home across $z$ edges on the simple path from the playground to his home. You have a map of Treeland where each vertex is labelled from $1$ to $n$. Find the number of triplets $(a, b, c)$ such that vertices $a, b, c$ could be Chef's home, his school and the playground respectively. If there is no such triplet, Chef may have miscounted some edges and you should output $0$. ### Input - The first line contains $t$, the number of test cases. $t$ cases follow. - The first line of each test case contains four integers $n, x, y, z$. - $n - 1$ lines follow, each with a pair of integers $u$ and $v$ denoting that there is an edge between $u$ and $v$. ### Output - For each testcase, output a single line containing the number of triplets which satisfy Chef's description. ### Constraints - $1 \leq t \leq 1000$ - $3 \leq n \leq 10^5$ - $1 \leq x, y, z \leq n - 1$ - Sum of $n$ over all test cases does not exceed $10^5$. ### Sample Input 2 7 4 3 3 1 2 2 3 3 4 4 5 3 6 3 7 3 2 2 2 1 2 1 3 ### Sample Output 4 0 ### Explanation **Case 1:** There are 4 possibilities as illustrated below. Consider the orange vertex as Chef's home, the green vertex as Chef's school, and the blue vertex as the playground. ![sample](https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_i...) **Case 2:** There are no triplets that satisfy Chef's description.
|Tags||centroid-decomp, cole2019, dp+bitmask, medium-hard, meooow|
|Time Limit:||1.5 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, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.