题意:

给你个树,求每个点的权值和它所在的子树的权值有几个是互质的

n<=100000,权值<=100000

然后..

分解每个权值的质因数,丢到vector里..

dfs序弄一下

每次查询容斥+二分就行了..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    edge * next;
};
edge * li[100005];
int a[100005];
int top=0;
edge * new_edge()
{
    static edge a[200005];
    return &a[top++];
}
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
vector<int> primes[100005];
vector<int> c[100005];
int dfn[100005];
int vis[100005];
int size[100005];
int sum=0;
void dfs(int x)
{
    vis[sum]=x;
    dfn[x]=sum;
    sum++;
    size[x]=1;
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (dfn[t->y]==-1)
        {
            dfs(t->y);
            size[x]+=size[t->y];
        }
    }
}
int ans[100005];
int lower_bounds(int x,int y)
{
    int l=0,r=c[x].size()-1;
    for (;l<=r;)
    {
        int mid=(l+r)/2;
        if (c[x][mid]<y) l=mid+1; else r=mid-1;
    }
    return r+1;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int zu;
    int n;
    int i;
    for (i=2;i<=100000;i++)
    {
        if (primes[i].size()==0)
        {
            int j;
            for (j=i;j<=100000;j+=i)
            {
                primes[j].push_back(i);
            }
        }
    }
    for (zu=1;scanf("%d",&n)!=-1;zu++)
    {
        top=0;
        memset(li,0,sizeof(li));
        int i;
        for (i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            insert_edge(x,y);
        }
        for (i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sum=0;
        memset(dfn,-1,sizeof(dfn));
        dfs(0);
        for (i=0;i<=100000;i++)
        {
            c[i].clear();
        }
        for (i=0;i<n;i++)
        {
            int now=vis[i];
            int j;
            int t=primes[a[now]].size();
            for (j=0;j<(1<<t);j++)
            {
                int p=1;
                int k;
                for (k=0;k<t;k++)
                {
                    if ((1<<k)&j) p=p*primes[a[now]][k];
                }
                c[p].push_back(i);
            }
        }
        for (i=0;i<n;i++)
        {
            int now=vis[i];
            int sum=0;
            int j;
            int t=primes[a[now]].size();
            for (j=0;j<(1<<t);j++)
            {
                int p=1;
                int k;
                int flag=1;
                for (k=0;k<t;k++)
                {
                    if ((1<<k)&j)
                    {
                        p=p*primes[a[now]][k];
                        flag*=-1;
                    }
                }
                sum+=flag*(lower_bound(c[p].begin(),c[p].end(),i+size[vis[i]])-lower_bound(c[p].begin(),c[p].end(),i));
            }
            ans[vis[i]]=sum;
        }
        printf("Case #%d: ",zu);
        for (i=0;i<n-1;i++)
        {
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[i]);
    }
}