孤独的树 树形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 ;
}
更多推荐
牛客xb赛48 F 孤独的树 树形dp 处理森林 筛法
发布评论