CSESProblemSet/main.cpp at master · Anton-Tarazi/CSESProblemSet · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
const int INF = 1e7;

void dfs(int node, int pred, vector<vector<int>> &tree, vector<int> &values, vector<vector<int>> &dp) {

    for (int neighbor: tree[node]) {
        if (neighbor != pred)
            dfs(neighbor, node, tree, values, dp);
    }


    for (int val = 1; val <= 10000; val++) {

        int cost = val == values[node] ? 0 : val;

        for (int neighbor: tree[node]) {

            if (neighbor == pred)continue;

            int min_neighbor_cost = INF;
            for (int neighbor_val = 1; neighbor_val <= 10000; neighbor_val++) {
                if (gcd(val, neighbor_val) > 1) {
                    min_neighbor_cost = min(min_neighbor_cost, dp[neighbor][neighbor_val]);
                }
            }

            cost += min_neighbor_cost;

        }

        dp[node][val] = cost;

    }


}


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

#ifdef LOCAL
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif

    int n;
    cin >> n;
    vector<int> values(n + 1);
    vector<vector<int>> tree(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> values[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }


    vector<vector<int>> dp(n + 1, vector<int> (10001, INF));

    dfs(1, -1, tree, values, dp);

    int min_val = INF;
    for (int i = 1; i <= 10000; i++) {
        min_val = min(min_val, dp[1][i]);
    }
    cout << min_val << endl;


    return 0;
}