题解 | #小美的树上染色#

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 1e5 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e9 + 7;

//md怎么一眼树形dp的
ll dp[N][2];
int st[N];
vector<ll>ed[N];
ll a[N], cnt;
//贪心
//从下向上贪心, 有的直接加上即可
void dfs(int u, int fa)
{
	for(auto it : ed[u])
	{
		if(it == fa) continue;
		dfs(it, u);
		ll s = a[it] * a[u];
		ll o = sqrt(s);
		if(o * o == s && st[it] == 0 && st[u] == 0)
		{
			st[it] = 1;
			st[u] = 1;
			cnt += 2;
		}
	}
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n - 1; i ++) 
	{
		int u, v;
		cin >> u >> v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	dfs(1, -1);
	cout << cnt << endl;
	return 0;
}