Tree House THOUSES SOLUTION

Tree House THOUSES Codechef

There is a large tree house in an unknown world. It is ruled by the great emperor KZS. It consists of N nodes numbered from 1 to N in which the people of that world reside. The nodes are organized in a tree structure rooted at node 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 is X.
All immediate children of any node have pairwise distinct values.
For every node with at least one immediate child, the 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) of two positive integers a and b is equal to the largest integer d such that both integers a and b are divisible by d.

Print the sum of all values, modulo 109+7.

Input
The first line contains an integer T, the number of test cases. T testcases follow.
The first line of each test contains two integers N and X.
Each of the following N−1 lines contains two integers u and v, denoting an edge between nodes u and v.
Output
For each test case, print the sum of values, modulo 109+7.
Constraints
1≤T≤15
2≤N≤3⋅105
1≤X≤109
1≤u,v≤N and u≠v
The given edges form a tree
The sum of N over all test cases doesn’t exceed 3⋅105.
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, we will give values 1, 2, 3 to the nodes 2, 3 and 4 respectively. So, the total sum will be 1+1+2+3=7.

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

close
error: Content is protected !!