博客

题意：给一个有根树（树根为








1










$1$
），每一个节点有一个点权（









1


<

=



w


[


i


]


<

=






10






5
















$1<=w[i]<=10^5$
），问一个节点








u










$u$
与它的子树上面所有节点互素的数有都少个？

分析：暴力判断每一个节点与它所有子树上面的点互素的数的个数，暴力找出









c


n


t


[


d




]











$cnt[d]$
：这个子树中








d












$d$
的倍数的个数。那么接下来可以容斥或者莫比乌斯反演搞定。对于每一个









u











$u$
，都要维护所有的








c


n


t


[


d




]










$cnt[d]$
怎么搞定？

由于遍历一棵树的过程是一个








d




f




s










$dfs$
，当前需要找的








c


n


t










$cnt$
就是遍历这棵子树后的








c


n


t










$cnt$
与遍历这棵子树前的








c


n


t










$cnt$
的差。换句话说，需要的答案，就是从根节点到这棵子树的所有节点中与当前节点互素的数的个数-从根节点到这个节点前的所有节点中与当前节点互素的个数。

#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;
}