自动搬运

查看原文

来自洛谷，原作者为

	yywlp 快递组万岁！！！

搬运于2025-08-24 23:00:27，当前版本为作者最后更新于2024-03-29 17:44:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

一句话总结：质因数分解后建模，树上启发式合并。

先考虑不在树上该如何解决。

假设现在数字分为两组 $S,T$（看成是两颗子树中的数）。

我们对其中的每个数字质因数分解，并且每个质因子只保留一位，具体地，假设一个数为

$$c_i=p_1^{a_1}\times p_2^{a_2}\times \dots \times p_n^{a_n} $$

那么我们把它变成

$$c_i'=p_1\times p_2\times \dots \times p_n$$

对这个 $c_i$ 我们向 $c_i'$ 的所有因数连边，可以发现，因为

$$2\times 3\times 5\times 7\times 11\times 13\times 17=510510>500000 $$

所以一个数在变形后最多只有 $6$ 个质因子，那么它的因数个数最大就为

$$\binom{6}{1}+\binom{6}{2}+\dots+\binom{6}{6}=63$$

所以一个数最多产生 $63$ 条边。

处理完所有数后发现被连了边的数的因子中没有质数的平方。我们遍历这些数。对于一个数 $x$，设 $T$ 中向 $x$ 连边的数的集合为 $Q$，$S$ 中向 $x$ 连边的数的集合为 $P$。

如果 $x$ 有奇数个质因子就会产生贡献：

$$\sum_{x\in Q}\sum_{y\in P}x\times y$$

如果 $x$ 有偶数个质因子就会产生贡献：

$$-\sum_{x\in Q}\sum_{y\in P}x\times y$$

这两个求和实际上是可以写成这样的：

$$\sum_{x\in Q}x\sum_{y\in P}y$$

那么求个和乘起来即可。

为什么这样做呢？我们考虑两个数 $a,b$，先对它们做最开始的处理变成 $a',b'$。不难发现，如果 $\gcd(a,b)>1$ 那么 $\gcd(a',b')>1$，所以我们现在只需要判断 $a',b'$ 的关系，按照上面的式子，在

$$p_1,p_2\dots p_n$$

的地方 $a',b'$ 都会被统计进答案，这明显算多了，但是在

$$p_1p_2,p_1p_3\dots p_np_{n-1}$$

的地方 $a',b'$ 又产生了负贡献，到这里已经可以发现这个其实就是容斥了。

会算重的质因子 $a',b'$ 一定都有，那么这些质因子组合出来的数同样也是 $a',b'$ 的因子，所以按照这样算完刚好满足容斥的式子，也即每一对数刚好被贡献了一次。时间复杂度 $\Theta (n)$ 有一个 $63$ 的常数。

放在树上只需要加一个启发式合并，在加一个数的时候先计算答案再把这个数要连的边加上即可，多一个 $\log$。

总复杂度 $\Theta (n\log{n})$ 有一个 $63$ 的常数，不过因为质因子分解几乎卡不满，所以会稍微快一点点，勉强通过。

但是这题如果直接按因数建虚树也能过，只是常数会大，为了尽量卡这种做法我就把时间调的比较小了QAQ。

不过有人写 $\Theta(n)$ 的虚树加上卡常依然能过，只能说我这道题出的真的不好，考虑的太少了QAQ。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=2e5+10,N=5e5+10,mod=998244353;
int n,a[M];
vector<int>G[M];
int p[N],isp[N],fr[N],mu[N];
vector<int>r1[N],rc[N];
LL pb[N],pc[N][20];
LL b[M],c[M];
int sz[M],son[M];
bool pd[N];
void dfs(int k,int m,int last,int sum,vector<int>&ps,vector<int>&st){
	if(m-k>(int)st.size()-last)return;
	if(k==m){
		ps.push_back(sum);
		return;
	}
	for(int i=last;i<(int)st.size();i++){
		dfs(k+1,m,i+1,sum*st[i],ps,st);
	}
}
void init(){
	isp[1]=mu[1]=1;
	for(int i=2;i<N;i++){
		if(!isp[i])p[++p[0]]=i,fr[i]=i,mu[i]=-1;
		for(int j=1;j<=p[0]&&i*p[j]<N;j++){
			isp[i*p[j]]=true;
			fr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
			mu[i*p[j]]=-mu[i];
		}
		int s=i;
		if(pd[s]){
			while(s>1){
				int np=fr[s];
				while(fr[s]==np)s/=np;
				r1[i].push_back(np);
			}
			for(int j=1;j<=(int)r1[i].size();j++)dfs(0,j,0,1,rc[i],r1[i]);
		}
	}
}
void init(int u,int f){
	sz[u]=1;
	for(int v:G[u]){
		if(v==f)continue;
		init(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
}
void dfs_count(int u,int f,int fr){
	for(int v:rc[a[u]])b[fr]-=mu[v]*pb[v]%mod*a[u]%mod,b[fr]%=mod;
	for(int v:G[u]){
		if(v==f)continue;
		dfs_count(v,u,fr);
	}
}
void dfs_add(int u,int f){
	for(int v:rc[a[u]])pb[v]+=a[u];
	for(int v:G[u]){
		if(v==f)continue;
		dfs_add(v,u);
	}
}
void dfs_del(int u,int f){
	for(int v:rc[a[u]])pb[v]-=a[u];
	for(int v:G[u]){
		if(v==f)continue;
		dfs_del(v,u);
	}
}
void dfs(int u,int f){
	for(int v:G[u]){
		if(v==f||v==son[u])continue;
		dfs(v,u);
		dfs_del(v,u);
	}
	if(son[u]){
		dfs(son[u],u);
		for(int v:rc[a[u]]){
			b[u]-=mu[v]*pb[v]%mod*a[u]%mod;
			b[u]%=mod;
			pb[v]+=a[u];
		}
		for(int v:G[u]){
			if(v==f||v==son[u])continue;
			dfs_count(v,u,u);
			dfs_add(v,u);
		}
	}else for(int v:rc[a[u]])pb[v]+=a[u];
}
int read() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;       
		ch = getchar();              
	}
	while (ch >= '0' && ch <= '9') {  
		x = x * 10 + (ch - '0'); 
		ch = getchar();  
	}
	return x * w;  
}
void write(LL x) {
	if (x < 0) {  
		x = -x;
		putchar('-');
	}
	if (x > 9) write(x / 10); 
	putchar(x % 10 + '0');  
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=read(),pd[a[i]]=true;
	init();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		G[u].push_back(v),G[v].push_back(u);
	}
	init(1,0);
	dfs(1,0);
	for(int i=1;i<=n;i++)write((b[i]+mod)%mod),putchar('\n');
	return 0;
}