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
5
1 2
1 3
2 4
2 5
6 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;
}