题意:给一个有根树(树根为
1
),每一个节点有一个点权(
1
<
=
w
[
i
]
<
=
10
5
),问一个节点
u
与它的子树上面所有节点互素的数有都少个?
分析:暴力判断每一个节点与它所有子树上面的点互素的数的个数,暴力找出
c
n
t
[
d
]
:这个子树中
d
的倍数的个数。那么接下来可以容斥或者莫比乌斯反演搞定。对于每一个
u
,都要维护所有的
c
n
t
[
d
]
怎么搞定?
由于遍历一棵树的过程是一个
d
f
s
,当前需要找的
c
n
t
就是遍历这棵子树后的
c
n
t
与遍历这棵子树前的
c
n
t
的差。换句话说,需要的答案,就是从根节点到这棵子树的所有节点中与当前节点互素的数的个数-从根节点到这个节点前的所有节点中与当前节点互素的个数。
#include <bits/stdc++.h>
#define LL long long
#define FOR(i,x,y) for(int i = x;i < y;++ i)
#define IFOR(i,x,y) for(int i = x;i > y;-- i)
using namespace std;
const int maxn = 100010;
int prime[maxn],mu[maxn];
bool check[maxn];
void Mobius(){
memset(check,false,sizeof(check));
prime[0] = 0;
FOR(i,2,maxn){
if(!check[i]){
prime[++prime[0]] = i;
mu[i] = -1;
}
FOR(j,1,prime[0]+1){
if(i*prime[j] >= maxn) break;
check[i*prime[j]] = true;
if(i%prime[j]){
mu[i*prime[j]] = -mu[i];
}
else{
mu[i] = 0;
break;
}
}
}
}
vector <int> G[maxn];
int cnt[maxn],w[maxn],sum;
void Get_Fac(int* fac,int& fac_cnt,int num){
FOR(i,1,prime[0]+1){
if(prime[i]*prime[i] > num) break;
if(num%prime[i] == 0) fac[fac_cnt++] = prime[i];
while(num%prime[i] == 0) num /= prime[i];
}
if(num > 1) fac[fac_cnt++] = num;
}
int rong(int* fac,int fac_cnt,bool flag){
int res = 0;
int msk = (1<<fac_cnt);
FOR(i,1,msk){
int mult = 1,tot = 0;
FOR(j,0,fac_cnt){
if(i & (1<<j)) {mult *= fac[j];tot ++;}
}
if(tot%2) res += cnt[mult];
else res -= cnt[mult];
if(flag) cnt[mult] ++;
}
return (sum - res);
}
int ans[maxn],n;
void dfs(int u,int fa){
int fac[20],fac_cnt = 0;
Get_Fac(fac,fac_cnt,w[u]);
int l = rong(fac,fac_cnt,true);
sum ++;
FOR(i,0,(int)G[u].size()){
int v = G[u][i];
if(v == fa) continue;
dfs(v,u);
}
int r = rong(fac,fac_cnt,false);
ans[u] = r-l;
}
void init(){
FOR(i,0,maxn) G[i].clear();
FOR(i,1,n){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
FOR(i,1,n+1) scanf("%d",&w[i]);
}
void work(){
memset(cnt,0,sizeof(cnt));
dfs(1,-1);
sum = 0;
FOR(i,1,n+1){
printf(" %d",ans[i]);
}
printf("\n");
}
int main(){
//freopen("test.in","r",stdin);
int tCase = 0;
Mobius();
while(~scanf("%d",&n)){
printf("Case #%d:",++tCase);
init();
work();
}
return 0;
}