第一条题解（点赞）

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

const int MAXN = 100010;
vector<int> graph[MAXN];
int values[MAXN];
bool visited[MAXN];
int n;

int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}

pair<int, int> dfs_farthest(int u, int parent, int depth) {
pair<int, int> res = {depth, u};
for (int v : graph[u]) {
if (v != parent && visited[v]) {
auto temp = dfs_farthest(v, u, depth + 1);
if (temp.first > res.first) {
res = temp;
}
}
}
return res;
}

int compute_diameter(vector<int>& nodes) {
if (nodes.empty()) return 0;

for (int node : nodes) visited[node] = true;

int start = nodes[0];
auto farthest1 = dfs_farthest(start, -1, 0);
auto farthest2 = dfs_farthest(farthest1.second, -1, 0);

for (int node : nodes) visited[node] = false;

return farthest2.first + 1;

}

int main() {
cin >> n;

for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    graph[x].push_back(y);
    graph[y].push_back(x);
}

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

unordered_map<int, vector<int>> prime_to_nodes;

for (int i = 1; i <= n; i++) {
    int val = values[i];
    for (int p = 2; p * p <= val; p++) {
        if (val % p == 0) {
            prime_to_nodes[p].push_back(i);
            while (val % p == 0) {
                val /= p;
            }
        }
    }
    if (val > 1) {
        prime_to_nodes[val].push_back(i);
    }
}

int max_length = 0;

for (auto& [prime, nodes] : prime_to_nodes) {
    for (int node : nodes) {
        visited[node] = true;
    }
    vector<bool> component_visited(n + 1, false);
    for (int node : nodes) {
        if (!component_visited[node]) {
            vector<int> current_component;
            vector<int> stack = {node};
            component_visited[node] = true;
            
            while (!stack.empty()) {
                int u = stack.back();
                stack.pop_back();
                current_component.push_back(u);
                
                for (int v : graph[u]) {
                    if (visited[v] && !component_visited[v]) {
                        component_visited[v] = true;
                        stack.push_back(v);
                    }
                }
            }
            
            int diameter = compute_diameter(current_component);
            max_length = max(max_length, diameter);
        }
    }
    for (int node : nodes)  visited[node] = false;
}

cout << max_length << endl;
return 0;

}
（点赞）删除文本