孤独的树

NC235690. 孤独的树

描述

给出一棵 $n$ 个点 $n-1$ 条边的树。树的节点为 $1 \sim n$ ，节点 $i$ 具有权值 $val[i]$ 。每次操作选择一个节点 $i$ ，再选择 $val[i]$ 的一个质因子 $x$ ，然后令 $val[i] = val[i] \div x$ 。问：最少操作几次，才能让这棵树变成一棵孤独的树。

孤独的树的定义：不存在一条边连接的两个节点 $u\ v$ ， $gcd(val[u],val[v])>1$ 。

输入描述

第一行包含一个整数 $n\ (1\le n\le10^5)$ ，代表树的节点个数。

第二行包含 $n$ 个整数 $val[1],val[2],val[3],...,val[n]\ (1\le val[i]\le 10^5)$ ，分别表示 $n$ 个节点。

接下来包含 $n-1$ 行，每行包含两个整数 $u\ v$ ，表示这棵树的边。

输出描述

输出一行包含一个整数，代表最少操作次数。

示例1

输入:

输出:

说明:

如果对节点 $2$ 操作，需要 $3$ 次。对节点 $1$ 和 $3$ 分别操作 $1$ 次即可。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 128ms, 内存消耗: 6412K, 提交时间: 2022-04-22 20:57:57

#include<bits/stdc++.h>

using namespace std;

int n;
int ans;
int vl[100010];
vector<int>v[100010];

int sum(int x)
{
	int s = 0;
	for(int i = 2; i <= x; i ++ )
	{
		while(1)
		{
			if(x % i == 0) x /= i, s ++;
			else break;
		}
	}
	return s;
}

void dfs(int u, int pre)
{
	for(int i = 0; i < v[u].size(); i ++ )
	{
		if(v[u][i] == pre) continue;
		dfs(v[u][i], u);
		int s = __gcd(vl[u], vl[v[u][i]]);
		vl[u] /= s;
		int k = sum(s);
		ans += k;
	}
}

signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ ) cin >> vl[i];
	for(int i = 1; i <= n - 1; i ++ )
	{
		int x,y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 1);
	cout << ans;
	return 0;
}