# HDU 4812-D Tree-分治-[解题报告]HOJ

2016-03-14 15:06:36来源:[db:出处]作者:[db:作者]人点击

D Tree

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 106 + 3) equals to K?Can you help them in solving this problem?

There are several test cases, please process till EOF.Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N – 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.

There are several test cases, please process till EOF.Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N – 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.

5 602 5 2 3 31 21 32 42 55 22 5 2 3 31 21 32 42 5

3 4No solutionHint1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较，若第一个数字大小相同，则按照第二个数字大小进行比较，依次类推。2. 若出现栈溢出，推荐使用C++语言提交，并通过以下方式扩栈：#pragma comment(linker,"/STACK:102400000,102400000")