#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], res[N]; //dp[u][0]: u白色 dp[u][1]:u红色 bool vis[N]; 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) { vis[u] = 1; for (int i = e[u]; i; i = ne[i]) { int v(to[i]), wi(w[i]); if (!vis[u]) { dfs(v, u); dp[u][0] += res[v]; } } for (int i = e[u]; i; i = ne[i]) { int v(to[i]), wi(w[i]); if (v != fa && check(wi)) { dp[u][1] = max(dp[u][1], dp[u][0] - res[v] + dp[v][0] + 2); } } res[u] = max(dp[u][0], dp[u][1]); } 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); } int ans(0); for (int i = 1; i <= n; i++) { if (!vis[i]) { dfs(i, 0); ans += res[i]; } } for (int i = 1; i <= n; i++) cout << dp[i][0] << ' ' << dp[i][1] << '\n'; cout << ans; }