Tree House Solution For Free | THOUSES | May long Challenge 2021 | Codechef Solution | Latest Video

 

There is a large tree house in an unknown world. It is ruled by the great emperor KZS. It consists of N$N$ nodes numbered from 1$1$ to N$N$ in which the people of that world reside. The nodes are organized in a tree structure rooted at node 1$1$. You need to assign values to the nodes according to the wishes of emperor KZS which are as follows :-

• The value of node 1$1$ is X$X$.
• All immediate children of any node have pairwise distinct values.
• For every node with at least one immediate child, the gcd$gcd$ of the values of all immediate children is equal to the value of the node.
• The total sum of the values of all nodes should be minimum.

The greatest common divisor gcd(a,b)$gcd(a,b)$ of two positive integers a$a$ and b$b$ is equal to the largest integer d$d$ such that both integers a$a$ and b$b$ are divisible by d$d$.

Print the sum of all values, modulo 109+7${10}^9+7$.

Input

• The first line contains an integer T$T$, the number of test cases. T$T$ testcases follow.
• The first line of each test contains two integers N$N$ and X$X$.
• Each of the following N−1$N-1$ lines contains two integers u$u$ and v$v$, denoting an edge between nodes u$u$ and v$v$.

Output

• For each test case, print the sum of values, modulo 109+7${10}^9+7$.

Constraints

• 1≤T≤15$1\le T\le 15$
• 2≤N≤3⋅105$2\le N\le 3\cdot {10}^5$
• 1≤X≤109$1\le X\le {10}^9$
• 1≤u,v≤N$1\le u,v\le N$ and u≠v$u\ne v$
• The given edges form a tree
• The sum of N$N$ over all test cases doesn't exceed 3⋅105$3\cdot {10}^5$.

Subtasks

Subtask #1 (100 points): Original Constraints

Sample Input

2
4 1
1 2
1 3
1 4
8 1
1 2
1 3
2 4
2 5
5 6
5 7
7 8

Sample Output

7
11

Explanation

In test case 1$1$, we will give values 1$1$, 2$2$, 3$3$ to the nodes 2$2$, 3$3$ and 4$4$ respectively. So, the total sum will be 1+1+2+3=7$1+1+2+3=7$.

Condition For the Solution : Follow All our social Media Account, We are New. After getting enough Subscriber we will start Uploading the Solution without any Condition, Please Understand...

Website :- https://codedelhi.blogspot.com Telegram :- https://t.me/EngineerDelhi Facebook :- https://www.facebook.com/EngineerDelhi Instagram :- https://www.instagram.com/engineerdelhi

DM all the Screen Shots on Telegram, we will send the solution there, due to Community Guidelines of Codechef. We can not share here....

Author:2★skywalker_

Date Added:14-04-2021

Time Limit:1 secs

Source Limit:50000 Bytes

Languages:CPP14, C, JAVA, PYTH 3.6, PYTH, CS2, ADA, PYPY, PYP3, TEXT, CPP17, PAS fpc, RUBY, PHP, NODEJS, GO, TCL, HASK, PERL, SCALA, kotlin, BASH, JS, PAS gpc, BF, LISP sbcl, CLOJ, LUA, D, R, CAML, rust, ASM, FORT, FS, LISP clisp, SQL, swift, SCM guile, PERL6, CLPS, WSPC, ERL, ICK, NICE, PRLG, ICON, PIKE, COB, SCM chicken, SCM qobi, ST, NEM, SQLQ