首页 > 代码库 > HDU5468(dfs序+容斥原理)

HDU5468(dfs序+容斥原理)

2024-08-11 00:57:30   218人阅读

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 n (1≤n≤105), after that has n−1 lines, each line has two numbers a and b (1≤a,b≤n), representing that vertex a is connect with vertex b. Then the next line has n numbers, the ith number indicates the value of the ith vertex. Values of vertices are not less than 1 and not more than 105.
 

 

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
5
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\n",res[n-1]);    }        return 0;}

 

 

 

HDU5468(dfs序+容斥原理)


联系
我们