#P1534. 2023.09.03-ali-第三题-塔子哥的树
2023.09.03-ali-第三题-塔子哥的树
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥有一棵树,树上每个结点都有一个权值,权值是 3 或者 5 ,
现在,塔子哥想问你,对于每条路径,路径上的点的权值的最小公倍数之和是多少
第一行,一个整数 n(1≤n≤105),表示树中结点数量。
第二行, n 个整数,第 i 个整数表示第 i 个结点的权值 ai(ai=3 或者 ai=5)
接下来 n−1 行,第 i 行两个整数 ui,vi(1≤ui,vi≤n) 表示结点 ui 和 vi 之间有一条边。
一个整数,表示所有路径上的点的权值的最小公倍数之和
输入
3
5 3 3
2 1
3 2
输出
33
说明
路径 1−2 的权值最小公倍数为:lcm(5,3)=15
路径 2−3 的权值最小公倍数为:lcm(3,3)=3
路径 1−2−3 的权值最小公倍数为:lcm(5,3,3)=15
15+15+3=33
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.