思路：深度优先搜索

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

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

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

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

时间复杂度：$O(n)$

cpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> vis(n);

    int cnt = 0;
    function<void(int)> dfs = [&](int u) {
        vis[u] = 1;
        cnt += 1;
        for (int v: g[u]) {
            if (vis[v] || a[v] != a[u]) continue;
            dfs(v);
        }
    };

    long long last_path = 1ll * n * (n - 1) / 2;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;

        cnt = 0;
        dfs(i);
   
        long long path = 1ll * cnt * (cnt - 1) / 2;
        last_path -= path;
        ans += path * a[i];
    }

    ans += last_path * 15;

    cout << ans << "\n";

    return 0;
}

java

import java.util.*;
// 注意类名必须为Main
class Main{
    static ArrayList<Integer>[] arr;
    static int[] weight;
    static boolean[] visit;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        arr = new ArrayList[n];
        Arrays.setAll(arr,e->new ArrayList<>());
        weight = new int[n];
        visit = new boolean[n];
        for (int i = 0; i < n; i++) {
            weight[i] = in.nextInt();
        }
        for (int i = 0; i < n-1; i++) {
            int node1 = in.nextInt()-1;
            int node2 = in.nextInt()-1;
            arr[node1].add(node2);
            arr[node2].add(node1);
        }
        long ans = 0;
        long allRoad = (long) n * (n - 1) / 2;
        for (int i = 0; i < n; i++) {
            if(!visit[i]){
                cnt = 0;
                dfs(i);
                long temp = (long) cnt * (cnt - 1) / 2;
                ans += temp * weight[i];
                allRoad -= temp;
            }
        }
        ans += (allRoad)*15;
        System.out.println(ans);
    }
    static int cnt;
    private static void dfs(int root){
        cnt++;
        visit[root] = true;
        for (Integer node : arr[root]){
            if(!visit[node] && weight[node] == weight[root]){
                dfs(node);
            }
        }
    }
}

python

n = int(input())
ws = [0] + [int(it) for it in input().split()]
edges = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = input().split()
    u, v = int(u), int(v)
    edges[u].append(v)
    edges[v].append(u)


def search(index, value, isvisit):
    isvisit[index] = True
    if ws[index] != value:
        return 0
    ans = 1
    for u in edges[index]:
        if not isvisit[u]:
            ans += search(u, value, isvisit)
    return ans


isvisit = [False] * (n + 1)
edge3, edge5 = 0, 0
for u in range(1, n + 1):
    if not isvisit[u]:
        node = search(u, 3, isvisit)
        edge3 += node * (node - 1) // 2

isvisit = [False] * (n + 1)
for u in range(1, n + 1):
    if not isvisit[u]:
        node = search(u, 5, isvisit)
        edge5 += node * (node - 1) // 2

print(3 * edge3 + 5 * edge5 + 15 * (n * (n - 1) // 2 - edge3 - edge5))

题目描述

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

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

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示树中结点数量。

第二行， $n$ 个整数，第 $i$ 个整数表示第 $i$ 个结点的权值 $a_i(a_i=3$ 或者 $a_i=5)$

接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i(1 \leq u_i,v_i \leq n)$ 表示结点 $u_i$ 和 $v_i$ 之间有一条边。

输出描述

一个整数，表示所有路径上的点的权值的最小公倍数之和

样例

输入

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