#include <iostream> #include <cmath> #define int long long using namespace std; const int N(1e5 + 5); const int dN(N << 1); int dp[N][2]; //dp[u][0]: u白色 dp[u][1]:u红色 int a[N], e[dN], ne[dN], to[dN], w[dN], id; void add(int u, int v) { to[++id] = v; w[id] = a[u] * a[v]; ne[id] = e[u]; e[u] = id; } inline bool check(int x) { int y(sqrt(x) + 0.5); return y * y == x; } void dfs(int u, int fa) { for (int i = e[u]; i; i = ne[i]) { int v(to[i]), wi(w[i]); if (v != fa) { dfs(v, u); dp[u][0] = max(dp[u][0], max(dp[v][0], dp[v][1])); if (check(wi)) dp[u][1] = max(dp[u][1], dp[v][0] + 2); } } } signed main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; add(u, v); add(v, u); } dfs(1, 0); cout << max(dp[1][0], dp[1][1]); }