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

hdu 5468(dfs序+容斥原理)

2024-08-15 10:36:25   218人阅读

Puzzled Elena

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


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
51 21 32 42 56 2 3 4 5
 

 

Sample Output
Case #1: 1 1 0 0 0
 

 

Source
2015 ACM/ICPC Asia Regional Shanghai Online
 
题意:给定 n 个结点 n-1条边的一棵树 ,每个结点都有一个 value，问每个节点的子节点的value与其value互素的个数有多少?
题解:我们可以先预处理出 1 ~ 10^5 内所有整数的因子,然后进行 DFS，当进入结点 u 时,记录当前与 u 不互素的数的个数为 a ，出节点 u 时,记录这时与 u不互素的个数为b，那么 u 的子树中 与 value[u] 不互素的个数就为 b-a ，当前结点 u 的子节点结点个数为 s,那么与 其互素的数个数为 s - (b-a).这里用一个 cnt[i]数组记录当前含有因数 i 的结点的个数,每次退出结点 u 的时候要将含有其因子的数量累加.还有就是当 val[u] == 1时,他与本身互素,答案 +1 .
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <bits/stdc++.h>using namespace std;typedef long long  LL;const int N = 100005;vector <int> factor[N];vector <int> edge[N];void init(){    for(int i=2;i<N;i++){        factor[i].clear();        int n = i;        for(int j=2;j*j<=n;j++){            if(n%j==0){                factor[i].push_back(j);                while(n%j==0) n/=j;            }        }        if(n>1) factor[i].push_back(n);    }}int cnt[N]; ///cnt[i]表示遍历到当前结点时候，含有因数i的结点个数。int val[N];int ans[N];int solve(int n,int val){    int len = factor[n].size(),ans=0;    for(int i=1;i<(1<<len);i++){        int odd = 0;        int mul = 1;        for(int j=0;j<len;j++){            if((i>>j)&1){                odd++;                mul*=factor[n][j];            }        }        if(odd&1){            ans+=cnt[mul];        }        else ans-=cnt[mul];        cnt[mul]+=val; /// val = 1 代表退出当前结点时把因子加上    }    return ans;}int dfs(int u,int pre){    int L = solve(val[u],0);  ///第一次遍历到 u,拥有与 u 相同的因子个数    int s = 0; ///s 代表当前结点下的子节点数目    for(int i=0;i<edge[u].size();i++){        int v = edge[u][i];        if(v==pre) continue;        s+=dfs(v,u);    }    int R = solve(val[u],1);    ans[u] = s - (R-L);    if(val[u]==1) ans[u]++;    return s+1;}int main(){    init();    int n,t = 1;    while(scanf("%d",&n)!=EOF){        memset(cnt,0,sizeof(cnt));        for(int i=1;i<=n;i++) edge[i].clear();        for(int i=1;i<n;i++){            int u,v;            scanf("%d%d",&u,&v);            edge[u].push_back(v);            edge[v].push_back(u);        }        for(int i=1;i<=n;i++){            scanf("%d",&val[i]);        }        dfs(1,-1);        bool flag = true;        printf("Case #%d: ",t++);        for(int i=1;i<=n;i++){            if(!flag) printf(" ");            flag = false;            printf("%d",ans[i]);        }        printf("\n");    }    return 0;}

 

hdu 5468(dfs序+容斥原理)


联系
我们