2025“钉耙编程”中国大学生算法设计暑期联赛（1）——树上LCM · znzryb
## 思路讲解
三个集合的容斥原理
$\left | A \cup B \cup C \right | = \left | A \right | + \left | B \right | + \left | C \right | - \left | A \cap B \right | - \left | A \cap C \right | - \left | B \cap C \right | + \left | A \cap B \cap C \right | $
那么不难发现规律，就是奇加偶减。这就是这段代码的由来。
```cpp
ll cn=bi.count();
if(cn%2==1) del+=(sz+1)*sz/2;
else del-=(sz+1)*(sz)/2;
```
那么直接计算合法路径数量比较难，但是我们可以枚举不合法子集。如果s是101（二进制），那么就是第一个素因子要不符合要求（LCM只关注这些数当中的最大的，你可以理解为对素因子取了一个并集，那么gcd就是取了一个交集）。
```cpp
// s如果这一位是1，就代表这一位的质因数必须不满足要求
FOR(s,0,(1<<siz)-1){
vb vis(N+5,0);
bitset<11> bi(s);
// 检查该数字（该点）是否满足要求
auto check=[&](ll u)->bool{
FOR(i,0,siz-1){
if(!bi[i]) continue;
// 该数不满足要求，因为我们要求这一位质因数数量缺失，或者太多
if(fach[u][i]==cnt[i]){
return false;
}
}
return true;
};
FOR(u,1,N){
if(vis[u]) continue;
if(!valid[u]) continue;
vis[u]=true;
if(!check(u)) continue;
queue<ll> q;q.push(u);
ll sz=0; // 维护联通块内的点的数量
while(!q.empty()){
ll u=q.front();q.pop();
vis[u]=true;
++sz;
for(auto v:g[u]){
if(vis[v]) continue;
if(!valid[v]) continue;
if(!check(v)) continue;
q.push(v);
}
}
// sz*(sz-1)/2+sz
ll cn=bi.count();
if(cn%2==1) del+=(sz+1)*sz/2;
else del-=(sz+1)*(sz)/2;
// ans+=(sz+1)*sz/2;
}
#ifdef LOCAL
debug(del);
#endif
}
ll ans=-del;
cout<<ans<<"\n";
}
```
## AC代码
[https://acm.hdu.edu.cn/contest/view-code?cid=1172&rid=22776](https://acm.hdu.edu.cn/contest/view-code?cid=1172&rid=22776)
::: 源代码
```cpp
// Problem: 树上LCM
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1172&pid=1007
// Memory Limit: 524288 KB
// Time Limit: 2000 ms
// by gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
constexpr ll MAXN=(ll)3e5+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll MAXV=(ll)1e6+10;
constexpr ll MAXM=(ll)2e6+10;
constexpr ll mod=(ll)1e9+7; // 998244353
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN];
/*
2*3*5*7*11*13*17*19*23-1e7
213092870.0
所以说不可能超过9位（素因数）
思路总结来说就是容斥原理
*/
// minp[i] 存储的是i的最小素因数
vector<ll> minp,primes;
void sieve(ll n){
minp.assign(n+5,0);
for(int i=2;i<=n;++i){
if(minp[i]==0){ // 是素数
minp[i]=i;
primes.push_back(i);
}
for(auto p:primes){
if(i*p>n){ // 超范围了
break;
}
minp[i*p]=p;
// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
// i * p_next = (p * k) * p_next 最小的应该是p
if(p==minp[i]){
break;
}
}
}
}
inline void __(){
cin>>N>>X;
vector<vector<ll> > g(N+5);
FOR(i,1,N-1){
ll u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
vb valid(N+5,0);
FOR(i,1,N){
cin>>A[i];
if(X%A[i]==0) valid[i]=true;
// 有不能整除节点的路径必然不能形成lcm=x
}
vector<ll> fac;ll siz=0;vll cnt;
auto primeDe=[&](ll x)->void{
while(x>1){
fac.push_back(minp[x]);
x/=minp[x];
}
sort(all(fac));
vll facu(all(fac));fac.resize(unique(all(fac))-fac.begin());
siz=SZ(fac);
for(auto &f:fac){
ll c=upper_bound(all(facu),f)-lower_bound(all(facu),f);
cnt.EB(c);
}
};
primeDe(X); // 返回去重的fac，以及因数计数cnt
vector<vector<ll> > fach(N+5,vector<ll>(10,0));
FOR(i,1,N){
if(!valid[i]) continue;
ll a=A[i];
while(a>1){
ll fa=minp[a];
a/=minp[a];
ll idx=lower_bound(all(fac),fa)-fac.begin();
fach[i][idx]++;
}
}
#ifdef LOCAL
FOR(i,0,SZ(fac)-1){
debug(fac[i]);
debug(cnt[i]);
}
#endif
ll del=0;
// s如果这一位是1，就代表这一位的质因数必须不满足要求
FOR(s,0,(1<<siz)-1){
vb vis(N+5,0);
bitset<11> bi(s);
// 检查该数字（该点）是否满足要求
auto check=[&](ll u)->bool{
FOR(i,0,siz-1){
if(!bi[i]) continue;
// 该数不满足要求，因为我们要求这一位质因数数量缺失，或者太多
if(fach[u][i]==cnt[i]){
return false;
}
}
return true;
};
FOR(u,1,N){
if(vis[u]) continue;
if(!valid[u]) continue;
vis[u]=true;
if(!check(u)) continue;
queue<ll> q;q.push(u);
ll sz=0; // 维护联通块内的点的数量
while(!q.empty()){
ll u=q.front();q.pop();
vis[u]=true;
++sz;
for(auto v:g[u]){
if(vis[v]) continue;
if(!valid[v]) continue;
if(!check(v)) continue;
q.push(v);
}
}
// sz*(sz-1)/2+sz
ll cn=bi.count();
if(cn%2==1) del+=(sz+1)*sz/2;
else del-=(sz+1)*(sz)/2;
// ans+=(sz+1)*sz/2;
}
#ifdef LOCAL
debug(del);
#endif
}
ll ans=-del;
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
sieve((ll)1E7+10);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1172&rid=22776
*/
```
:::
## 心路历程（WA，TLE，MLE……）