D Tree 程序的设计

Problem Description
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?

Input
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.

Output
For each test case, print a single line containing two integers a and b (where a < b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead.
For more information, please refer to the Sample Output below.

Sample Input
5 60
2 5 2 3 3
1 2
1 3
2 4
2 5
5 2
2 5 2 3 3
1 2
1 3
2 4
2 5

Sample Output
3 4
No solution

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
求救,kd-tree下的knn最近邻搜索具体是怎么工作的,求教!
2
elementUI tree能添加tag功能么,比如显示树下资源的数量
3
element-ui tree全部展开和全部收起功能的实现
0
翻转数据结构的树的节点,怎么利用C语言的程序的设计的形式来实现的
0
数据结构里的树的合并转移的算法,利用C语言的程序的设计的实现的方式怎么做?
0
el-tree中怎样阻止render下的事件传播
0
子树的条件的搜索问题,怎么使用C语言的程序的编写的代码的设计的方式加以有效地实现的
0
相似性的判断的算法,怎么判断图的节点上的相似性用C语言的程序的代码设计的程序怎么实现
0
根据规则扩展二叉树的实现原理,使用C语言的程序编写设计思想的方式怎么完成
0
判断二叉数的相似的遍历的问题,要求使用C语言的程序的设计的办法的解决的过程怎么做
0
难易程度的判断、打分的问题,要求使用C语言的程序的设计的思想原理来解决,怎么去实现的
0
输出最大的可见的树的一个算法的问题,怎么采用C语言的程序的编写的设计的方式来实现的
1
根据树T和K,计算顶点的问题怎么采用,C语言的程序的设计的思想的过程的方法来实现的呢?
0
对二叉树按照遍历的顺序来实现编码,怎么用C语言的程序的设计的代码的编写的过程的技术来实现的呢
0
判断一个tree是否存在相似性的问题,怎么用C语言的程序的编写来实现计算的
0
用C语言问题怎么做,Turing Tree
0
Minimum Spanning Tree程序怎么写的
0
用C语言解答 Minimum Spanning Tree
0
Color the Tree
0
Letter Tree程序怎么编写的