小白月赛最后一题，树形dp有两种方式做，第一种思维要求高一点，第二种代码麻烦一点。
解法一：
从树形结构自下而上观察本问题（上指的是树根，下指的是叶子）。
某个节点，与其子节点有公共的最大公因数，两个节点中必须要有一个要删除他们的最大公因数，删那个的对结果的贡献都是最大公因数的质数组成数。那么我们删哪一个呢?我们删父节点!
因为 删了父节点之后，因为我们是从叶子节点看起，删了父节点，这个gcd的影响就传不到父节点的父节点去了，而且还防止了删了这个子节点的gcd，别的子节点和父节点还有gcd或者这个gcd的因子
所以从叶子节点往上，我们只需要一直删父节点的gcd就行了，并且将删gcd的次数加到答案里
代码如下：十分优美
#include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 2e5 + 10, INF = 0x3f3f3f3f; int cnt[N]; //i 的质因子多少个 int w[N]; vector<int>g[N]; int n; int ans=0; void init() { for(int i=2;i<N;i++) { if(!cnt[i]) { for(int j=i;j<N;j+=i) { int t=j; while(t%i==0) cnt[j]++,t/=i; } } } } void dfs(int u,int fa) { for(auto x: g[u]) { if(x==fa) continue; dfs(x,u); ans+=cnt[__gcd(w[u],w[x])]; w[u]/=__gcd(w[u],w[x]); } } void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } dfs(1,-1); cout<<ans<<endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1;init(); //cin>>__; while (__--) { solve(); } return 0; }
**解法二：**维护每个最大的质因子组成的森林，用基础的区间dp来维护答案，我们用d p [ i ] [ 0 ] dp[i][0]dp[i][0]表示没有选i子树删了目前的质因子的最小次数，d p [ i ] [ 1 ] dp[i][1]dp[i][1]表示选了i子树删了目前质因子的最小次数。
状态转移为：d p [ u ] [ 1 ] = dp[u][1]=dp[u][1]=∑ m i n ( d p [ x ] [ 1 ] , d p [ x ] [ 0 ] ) + c n t \sum min(dp[x][1],dp[x][0])+cnt∑min(dp[x][1],dp[x][0])+cnt
d p [ u ] [ 0 ] = dp[u][0]=dp[u][0]=∑ d p [ x ] [ 1 ] \sum dp[x][1]∑dp[x][1]
代码如下：详情看注释
#include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 1e5 + 10, INF = 0x3f3f3f3f; int w[N]; int n; int prime[N];//欧拉筛存质数 bool st[N];//注意，prime[i]的节点之间可能不是相连的而是森林，所以维护st[i] int f[N][2]; int maxp[N];//这个数的最大的质因子 int cnt = 0; vector<int>g[N];//存树 vector<int>rk[N];//此时存质因子的节点有那些 void init() { for (int i = 2; i < N; i++) { if (!maxp[i]) prime[cnt++] = i, maxp[i] = i;//质数的最大的质因子是自己 for (int j = 0; j < cnt && prime[j]*i < N; j++) { maxp[i * prime[j]] = prime[j]; if (i % prime[j] == 0) break; } } } void dfs(int u, int fa, int p) { st[u] = 1; f[u][0] = 0; int t = w[u], c = 0; while (t % p == 0) { c++; t /= p; } f[u][1] = c; for (auto x : g[u]) { if (w[x] % p != 0 || x == fa || st[x]) continue; dfs(x, u, p); f[u][0] += f[x][1]; f[u][1] += min(f[x][1], f[x][0]); } } void solve() { cin >> n; init(); for (int i = 1; i <= n; i++) { cin >> w[i]; int t = w[i]; while (t > 1) { rk[maxp[t]].push_back(i);//预处理 t /= maxp[t]; } } for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } int ans = 0; for (int i = 0; i < cnt; i++) { for (auto x : rk[prime[i]]) { st[x] = 0; f[x][0] = 0; f[x][1] = 0; } for (auto x : rk[prime[i]]) { if (!st[x])//注意，prime[i]的节点之间可能不是相连的而是森林，所以维护st[i] { dfs(x, -1, prime[i]); ans += min(f[x][0], f[x][1]); } } } cout << ans << endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
