题目描述

小红有一棵树，树上每个结点都有一个权值，权值是 $3$ 或者 $5$ ，

现在，小红想问你，对于每条路径，路径上的点的权值的最小公倍数之和是多少

思路：深度优先搜索

对于每个点，通过 DFS 找到这个点所在的同权值连通块。

在这个连通块内的所有点，两两之间的路径的权值的最小公倍数必然是 $3$ 或 $5$ 。

对于剩余的跨同权值连通块的点，其路径的权值的最小公倍数必然是 $15$ 。

可以先计算同权值连通块内的路径数，然后拿所有点之间的路径数减去同权值连通块内的路径数，即跨连通块的路径数。