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

题目

传送门

题解思路

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

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

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

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

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

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

最后在根节点取min即可。

AC代码

#include
//#include
//priority_queue
#define PII pair<int,int>
#define ll long longusing namespace std;const int INF &＃61; 0x3f3f3f3f;
const int N &＃61; 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 &＃61; 2 ; i <&＃61; 1e5 &＃43; 5 ; i&＃43;&＃43; ){if (!np[i]){for (int j &＃61; i ; j <&＃61; 1e5 &＃43; 5 ; j &＃43;&＃61; i ){np[j] &＃61; 1 ; mnp[j] &＃61; i ; }}}
}
void dfs(int x , int p )
{vis[x].insert(p) ; int cnt &＃61; 0 ; while ( a[x] % p &＃61;&＃61; 0 )a[x]/&＃61;p,cnt&＃43;&＃43;;int sum1 &＃61; 0 ,sum0 &＃61; 0 ; for (int i &＃61; 0 ; i < head[x].size() ; i&＃43;&＃43; ){int sk &＃61; head[x][i] ;if ( !vis[sk].count(p) && a[sk] % p &＃61;&＃61; 0 ){dfs(sk,p) ; sum0 &＃43;&＃61; min(f[sk][0],f[sk][1]) ; sum1 &＃43;&＃61; f[sk][1] ; }}f[x][0] &＃61; sum1 ; f[x][1] &＃61; sum0 &＃43; cnt ;
}
void solve()
{si();int n ;cin >> n ; for (int i &＃61; 1 ; i <&＃61; n ; i&＃43;&＃43; )cin >> a[i] ; for (int i &＃61; 1 ; i < n ; i&＃43;&＃43; ){int t1 , t2 ;cin >> t1 >> t2 ; head[t1].push_back(t2) ; head[t2].push_back(t1) ; }int ans &＃61; 0 ; for (int i &＃61; 1 ; i <&＃61; n ; i&＃43;&＃43; ){while ( a[i] !&＃61; 1 ){int p &＃61; mnp[a[i]] ; if (!vis[i].count(p)){dfs(i,p) ; ans &＃43;&＃61; 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 ;
}