
ZOJ Problem Set  3824
Marjar University has decided to upgrade the infrastructure of school intranet by using fiberoptic technology. There are N buildings in the school. Each building will be installed with one router. These routers are connected by optical cables in such a way that there is exactly one path between any two routers. Each router should be initialized with an operating frequency F_{i} before it starts to work. Due to the limitations of hardware and environment, the operating frequency should be an integer number within [L_{i}, R_{i}]. In order to reduce the signal noise, the operating frequency of any two adjacent routers should be coprime. Edward is the headmaster of Marjar University. He is very interested in the number of different ways to initialize the operating frequency. Please write a program to help him! To make the report simple and neat, you only need to calculate the sum of F_{i} (modulo 1000000007) in all solutions for each router. InputThere are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains one integer N (1 <= N <= 50). The next line contains N integers L_{i} (1 <= L_{i} <= 50000). Then, the following line contains N integers R_{i} (L_{i} <= R_{i} <= 50000). For the next N  1 lines, each line contains two integers X_{i} and Y_{i}. That means there is an optical cable connecting router X_{i} and router Y_{i} (indexes are 1based). OutputFor each test case, output a line with N integers representing the sum of F_{i} (modulo 1000000007) in all solutions. Sample Input2 4 1 2 3 4 2 3 4 5 1 2 2 3 3 4 4 1 2 3 4 2 3 4 5 1 2 1 3 1 4 Sample Output5 10 14 19 10 23 31 41 HintIn the first sample test case, there are 4 ways to initialize the operating frequency:
Author: JIANG, Kai Source: The 2014 ACMICPC Asia Mudanjiang Regional Contest 