孤独的树（牛客月赛）"/>
孤独的树（牛客月赛）
小白月赛最后一题，树形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);//#endifint __ = 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);//#endifint __ = 1;//cin>>__;while (__--){solve();}return 0;
}更多推荐
孤独的树（牛客月赛）
发布评论