小白月赛最后一题，树形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;
}
