题干：

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

题目大意：

给出一棵树n个点,每个点上有权值。然后求每棵子树中与根节点互质，即gcd(a,b)=1的节点个数。

解题报告：

因为1e5以内的每个数的素因子个数不超过10个，所以可以对于每个数的不互素个数可以在O(10*2^10)内算出来，所以直接dfs序映射成一个序列然后按照题意求就行了。注意题目问的是gcd==1而不是互素，所以1和本身也是gcd==1的，所以val==1的时候需要ans++。

贴一个题解：

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

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

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
vector<int> vv[MAX];
int val[MAX],ans[MAX],num[MAX];
int dfn[MAX],in[MAX],out[MAX],id;
vector<int> fac[MAX];
void db() {
	for(int tar = 1; tar<MAX; tar++) {
		int x = tar;
		for(int i = 2; i*i<=x; i++) {
			if(x%i == 0) {
				fac[tar].pb(i);
				while(x%i==0) x/=i;
			}
		}
		if(x > 1) fac[tar].pb(x);
	}
}
int cal(int n,int tar) {
	int res = 0;
	int upp = 1<<fac[n].size(),up = fac[n].size();
	for(int bit = 1; bit<upp; bit++) {
		int cnt = 0,mul = 1;
		for(int i = 0; i<up; i++) {
			if(bit & (1<<i)) {
				cnt++;
				mul *= fac[n][i];
			} 
		}
		if(cnt & 1) res += num[mul];
		else res -= num[mul];
		num[mul] += tar;
	}
	return res;
}
int dfs(int cur,int rt) {
	int ans1 = cal(val[cur],0);
	int res = 0;
	int up = vv[cur].size();
	for(int i = 0; i<up; i++) {
		int v = vv[cur][i];
		if(v == rt) continue;
		res += dfs(v,cur);
	}
	int ans2 = cal(val[cur],1);
	ans[cur] = res - (ans2 - ans1);
	if(val[cur] == 1) ans[cur]++;
	return res+1;
}
int main()
{
	db();
	int n,iCase=0;
	while(~scanf("%d",&n)) {
		//init
		id=0;
		for(int i = 1; i<MAX; i++) num[i] = 0;
		for(int i = 1; i<=n; i++) vv[i].clear(),ans[i]=0;
		for(int a,b,i = 1; i<=n-1; i++) {
			scanf("%d%d",&a,&b);
			vv[a].pb(b);vv[b].pb(a);
		} 
		for(int i = 1; i<=n; i++) scanf("%d",val+i);
		dfs(1,-1);
		printf("Case #%d:",++iCase);
		for(int i = 1; i<=n; i++) printf(" %d",ans[i]); 
		printf("\n");	
	} 
	return 0 ;
}