2025“钉耙编程”中国大学生算法设计暑期联赛（1）——树上LCM

思路讲解

三个集合的容斥原理

$\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 | $

那么不难发现规律，就是奇加偶减。这就是这段代码的由来。

ll cn=bi.count();
if(cn%2==1) del+=(sz+1)*sz/2;
else del-=(sz+1)*(sz)/2;

那么直接计算合法路径数量比较难，但是我们可以枚举不合法子集。如果s是101（二进制），那么就是第一个素因子要不符合要求（LCM只关注这些数当中的最大的，你可以理解为对素因子取了一个并集，那么gcd就是取了一个交集）。

// 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

源代码

// 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……）