HDU5468(dfs序+容斥原理)

Puzzled Elena

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1162 Accepted Submission(s): 339

Problem Description

Since both Stefan and Damon fell in love with Elena, and it was really difficult for her to choose. Bonnie, her best friend, suggested her to throw a question to them, and she would choose the one who can solve it.

Suppose there is a tree with n vertices and n - 1 edges, and there is a value at each vertex. The root is vertex 1. Then for each vertex, could you tell me how many vertices of its subtree can be said to be co-prime with itself?
NOTES: Two vertices are said to be co-prime if their values' GCD (greatest common divisor) equals 1.

Input

There are multiply tests (no more than 8).
For each test, the first line has a number

Output

For each test, at first, please output "Case #k: ", k is the number of test. Then, please output one line with n numbers (separated by spaces), representing the answer of each vertex.

Sample Input

1 2

1 3

2 4

2 5

6 2 3 4 5

Sample Output

Case #1: 1 1 0 0 0

思路：该题涉及到一个典型问题.问x与S中有多少个数不互素。解决办法是将S中所有元素依次进行两个步骤：①将元素进行质因数分解。②将质因数可能产生的乘积的出现次数加1。最后将x进行质因数分解，利用容斥原理求解。具体方案见代码。

容斥原理在OJ中常解决两个典型问题：①求S中有多少个数与x不互素。②求1~m中有多少个数与n不互素。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN=100001;
typedef long long LL;
vector<LL> divisor[MAXN];
void prep()
{
    for(LL e=1;e<MAXN;e++)
    {
        LL x=e;
        for(LL i=2;i*i<=x;i++)    
        {
            if(x%i==0)
            {
                divisor[e].push_back(i);
                while(x%i==0)    x/=i;
            }
        }
        if(x>1)    divisor[e].push_back(x);
    }
}

vector<int> arc[MAXN];
int n,val[MAXN];
int cnt[MAXN],res[MAXN];
int cal(int n,int type)//求集合S中与n不互素的数的个数 
{
    int ans=0;
    for(LL mark=1;mark<(1<<divisor[n].size());mark++)
    {
        LL odd=0;
        LL mul=1;
        for(LL i=0;i<divisor[n].size();i++)
        {
            if(mark&(1<<i))
            {
                odd++;
                mul*=divisor[n][i];
            }
        }
        if(odd&1)    ans+=cnt[mul];
        else    ans-=cnt[mul];
        cnt[mul]+=type;
    }
    return ans;
}
int dfs(int u,int fa)
{
    int pre=cal(val[u],0);
    int s=0;
    for(int i=0;i<arc[u].size();i++)
    {
        int to=arc[u][i];
        if(to!=fa)
        {
            s+=dfs(to,u);
        }
    }
    int post=cal(val[u],1);
    res[u]=s-(post-pre);//以u为根的子树结点数目-(遍历u之前与u不互素的结点数目-遍历u之后与u不互素的结点数目) 
    if(val[u]==1)    res[u]++;//若u的值为1,那么u与自身互素 
    return s+1;
}
int main()
{
    prep();
    int cas=0;
    while(scanf("%d",&n)!=EOF)        
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)    arc[i].clear();
        for(int i=0;i<n-1;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            arc[u].push_back(v);
            arc[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
        }
        dfs(1,-1);
        printf("Case #%d: ",++cas);
        for(int i=1;i<n;i++)
        {
            printf("%d ",res[i]);    
        }        
        printf("%d
",res[n-1]);
    }    
    return 0;
}