https://ac.nowcoder.com/acm/contest/11225/F
方法1:
因为每次只能删去一个质因子,所以对每个质数x,包含x的val可把树分成若干个连通块,
在每个连通块内,点权变成val包含几个x,问题可转化成每个点要么拿要么不拿,相邻的两个点不能全不拿,dp即可
技巧:先预处理每个数的最大质因子,读入val时分解质因式,并在cnt数组中加入{i,s}
便利1-N质数,将数组中包含这个质数的val标记,进行dp即可
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl "\n"
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define debug(a) cout<<#a<<' '<<a<<endl;
#define cut cout<<"-------------------"<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N = 1e5+10;
const ll mod=1e9 + 7, inf = 0x3f3f3f3f;
mt19937 mrand(time(0));
int rnd(int x) { return mrand() % x;}
ll qmi(ll a,ll b,ll p) {ll res=1;a%=p; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%p;a=a*a%p;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// #define int ll
//2 3 5 7 11 13 17
vector<pii> cnt[N];
int val[N], n;
bool vis[N];
vector<int> g[N];
int dp[N][2]; // 1删,不能有两个0连着
int mi[N];// 最大质因子
bool st[N];
int sum[N];
void init()
{
for(int i = 2; i <N; i ++)
{
if(mi[i]) continue;
for(int j = i ; j < N; j += i)
mi[j] = i;
}
}
void dfs(int u)
{
vis[u] = 1;
dp[u][1] = sum[u];
dp[u][0] = 0;
for(int p : g[u])
{
if(!sum[p] || vis[p]) continue;
dfs(p);
dp[u][1] += min(dp[p][0], dp[p][1]);
dp[u][0] += dp[p][1];
}
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> val[i];
while(val[i] > 1)
{
int num = mi[val[i]];
pii res = {i, 0};
while(val[i] % num == 0)
res.se ++, val[i] /= num;
cnt[num].pb(res);
}
}
for(int i = 1; i < n; i ++)
{
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
ll ans = 0;
for(int pi = 1; pi < N; pi ++) // 质数
{
if(mi[pi] != pi || SZ(cnt[pi]) == 0) continue;
for(int i = 1; i <= n; i ++)
dp[i][0] = dp[i][1] = 0, st[i] = vis[i] = 0, sum[i] = 0;
for(pii t : cnt[pi]) st[t.fi] = 1, sum[t.fi] = t.se;
// for(int i = 1; i <= n; i ++)
for(pii t : cnt[pi])
{
int i = t.fi;
if(!vis[i] && st[i])
{
dfs(i);
ans += min(dp[i][0], dp[i][1]);
}
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
init();
int _;
_ = 1;
while(_--)
{
solve();
}
return 0;
}
方法2
一遍dfs即可(不懂这个的正确性)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl "\n"
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define debug(a) cout<<#a<<' '<<a<<endl;
#define cut cout<<"-------------------"<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N = 1e5+10;
const ll mod=1e9 + 7, inf = 0x3f3f3f3f;
mt19937 mrand(time(0));
int rnd(int x) { return mrand() % x;}
ll qmi(ll a,ll b,ll p) {ll res=1;a%=p; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%p;a=a*a%p;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//2 3 5 7 11 13 17
int n, val[N];
vector<int> g[N];
int ans = 0;
int cnt[N];
void dfs(int u, int fa)
{
for(int p : g[u])
{
if(p == fa) continue;
dfs(p, u);
int d = gcd(val[u], val[p]);
ans += cnt[d];
val[u] /= d;
}
}
void init()
{
for(int i = 1; i <= 100000; i ++)
{
int j = i;
for(int k = 2; k <= j / k; k ++)
{
if(j % k == 0)
{
while(j % k == 0 && j)
cnt[i] ++, j /= k;
}
}
if(j > 1)
cnt[i] ++;
}
// debug(cnt[2])
cin >> n;
for(int i = 1 ;i <= n; i ++)
cin >> val[i];
for(int i = 1; i < n; i ++)
{
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
dfs(1, -1);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
// cin>>_;
_ = 1;
while(_--)
{
init();
}
return 0;
}
这个mi数组求的是最大质因数吧
是了是了