頂点の木が与えられます。
木の頂点 には整数 が書かれています。
木の 番目の辺は頂点 と頂点 を結んでいます。
なる整数 に対して、次の問題を解いてください。
行出力せよ。
行目には、頂点 から頂点 までの最短パス上の最小公倍数を出力せよ。
8 1 2 3 4 5 6 7 8 1 2 1 6 2 3 2 4 2 5 4 7 4 8
1 2 6 4 10 6 28 8
例えば、頂点 から までの最短パス上の頂点に書かれている整数は です。 これらの最小公倍数は になります。
10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10
1 2 10 30 60 30 210 3 6 12
6 23 31 47 51 67 71 1 2 2 3 3 4 4 5 5 6
23 713 33511 1709061 114507087 130003121
答えは で割ったあまりであることに注意してください。