牛客xb赛48 F 孤独的树 树形dp 处理森林 筛法

孤独的树 树形dp 处理森林 筛法"/>

牛客xb赛48 F 孤独的树 树形dp 处理森林 筛法

题目

传送门

题解思路

因为N最大就是1e5，所以对与每个权值他最多只能有6个不同的质因子。
我们每次只能去除一个质因子，所以，如果要去除这个点的这种质因子就多次去除这个即可。

我们从最大的质因子不断往小删。这样就能O1获取我们此时到底要删谁。

有相同质因子的点可以构成森林（多个连通块），我们对每个连通块，每次都处理掉一种质因子，这样就能保证复杂度在Nlog(N)。

对于每个连通块处理同种质因子有树形dp来计算最小的次数，最后再累加。

dp[i][0] 表示以i为根节点的子树，根节点不进行删除操作使得满足题目条件的最小次数。

dp[i][1]就表示进行操作的最小次数。

最后在根节点取min即可。

AC代码

#include <bits/stdc++.h>
//#include <unordered_map>
//priority_queue
#define PII pair<int,int>
#define ll long longusing namespace std;const  int  INF =  0x3f3f3f3f;
const  int  N =  200100;
int a[N] ; 
vector <int> head[N] ;
set <int> vis[N] ; 
int f[N][3] ;  
int np[N] ; 
int mnp[N] ; 
void si()
{for (int i = 2 ; i <= 1e5 + 5 ; i++ ){if (!np[i]){for (int j = i ; j <= 1e5 + 5 ; j += i ){np[j] = 1 ; mnp[j] = i ; }}}
}
void dfs(int x , int p )
{vis[x].insert(p) ; int  cnt = 0 ; while ( a[x] % p == 0 )a[x]/=p,cnt++;int sum1 = 0 ,sum0 = 0 ; for (int i = 0 ; i < head[x].size() ; i++ ){int sk = head[x][i] ;if ( !vis[sk].count(p) && a[sk] % p == 0 ){dfs(sk,p) ; sum0 += min(f[sk][0],f[sk][1]) ; sum1 += f[sk][1] ; }}f[x][0] = sum1 ; f[x][1] = sum0 + cnt ; 
}
void solve()
{si();int n ;cin >> n ; for (int i = 1 ; i <= n ; i++ )cin >> a[i] ; for (int i = 1 ; i < n ; i++ ){int t1 , t2 ;cin >> t1 >> t2 ; head[t1].push_back(t2) ; head[t2].push_back(t1) ; }int ans = 0 ; for (int i = 1 ; i <= n ; i++ ){while ( a[i] != 1 ){int p = mnp[a[i]] ; if (!vis[i].count(p)){dfs(i,p) ; ans += min(f[i][1],f[i][0]) ; }}}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve() ;return 0 ;
}