考虑对一个集合求莫比乌斯反演的过程，最终答案即$\sum\limits_{d|ai}\mu(d)\cdot calc(d)$（calc(d)表示i子树中d倍数的个数）
dfs时维护当前遍历到的点中i倍数的个数，对i搜之前和i搜完后差分一下就可以得到i子树的信息，用上述式子计算即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define K 130 5 struct ji{ 6 int nex,to; 7 }edge[N<<1]; 8 int E,t,n,m,x,y,a[N],head[N],mu[N],vis[N],p[N],sum[N],ans[N],v[N][K],s[N][K]; 9 void add(int x,int y){ 10 edge[E].nex=head[x]; 11 edge[E].to=y; 12 head[x]=E++; 13 } 14 void dfs(int k,int fa){ 15 for(int i=1;i<=v[k][0];i++)s[k][i]=sum[v[k][i]]++; 16 for(int i=head[k];i!=-1;i=edge[i].nex) 17 if (edge[i].to!=fa)dfs(edge[i].to,k); 18 for(int i=1;i<=v[k][0];i++)ans[k]+=mu[v[k][i]]*(sum[v[k][i]]-s[k][i]); 19 } 20 int main(){ 21 mu[1]=1; 22 for(int i=2;i<N-4;i++){ 23 if (!vis[i]){ 24 mu[i]=-1; 25 p[++p[0]]=i; 26 } 27 for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){ 28 vis[i*p[j]]=1; 29 if (i%p[j]==0)break; 30 mu[i*p[j]]=-mu[i]; 31 } 32 } 33 while (scanf("%d",&n)!=EOF){ 34 E=0; 35 memset(head,-1,sizeof(head)); 36 memset(v,0,sizeof(v)); 37 memset(s,0,sizeof(s)); 38 memset(sum,0,sizeof(sum)); 39 memset(ans,0,sizeof(ans)); 40 for(int i=1;i<n;i++){ 41 scanf("%d%d",&x,&y); 42 add(x,y); 43 add(y,x); 44 } 45 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 46 for(int i=1;i<=n;i++){ 47 for(int j=1;j*j<=a[i];j++) 48 if (a[i]%j==0)v[i][++v[i][0]]=j; 49 for(int j=v[i][0];j;j--) 50 if (v[i][j]*v[i][j]<a[i])v[i][++v[i][0]]=a[i]/v[i][j]; 51 } 52 dfs(1,0); 53 printf("Case #%d:",++t); 54 for(int i=1;i<=n;i++)printf(" %d",ans[i]); 55 printf("\n"); 56 } 57 }