HDu 5468 Puzzled Elena前処理+深捜し+反発

Puzzled Elena
Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 641    Accepted Submission(s): 167
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
各数値の素因数(<=6)を前処理した後、反発(<64)のためにこれらの素因数からなる数値を前処理する.
1つの数に対してその質因子からなる数の係数を反発法で算出する(1 or-1)
各数値の係数と
dfs処理プロセス:
      与えられたツリーに対して1回の後順遍歴を行い,そのノードに入る前にそのノード数を記録する必要がある情報を読み出し,この点に戻ってから差分値を行うことがサブツリーで得られる値である.
このノードを離れるときは,このノードの数の前処理の結果(係数)を記録情報に加える.
計算したのは、このノードと非相質な数の個数です.だからもう一度減算すればいいです.特判=1の場合です.
記録された情報は、その数値の係数和である.複雑度64×n

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#define maxn 100007
using namespace std;
vector<int> pri[maxn],head[maxn],ty[maxn];
int num[maxn];


void init(){
    memset(num,0,sizeof(num));
    for(int i = 0;i < maxn; i++)
        pri[i].clear(),ty[i].clear();
    for(int i = 2;i < maxn ;i++){
        if(num[i] == 0){
            for(int j = i;j < maxn; j+=i){
                num[j] = 1;
                pri[j].push_back(i);
            }
        }
    }
    vector<int> x;
    for(int i = 2;i < maxn; i++){
        x.clear();
        for(int j = 0;j < pri[i].size(); j++){
            x.push_back(pri[i][j]);
        }
        pri[i].clear();
        int n = x.size();
        for(int j = 1;j < (1<<n); j++){
            int y = 1,f=0;
            for(int k = 0;k < n; k++){
                if(j&(1<<k)){
                    y *= x[k];
                    f++;
                }
            }
            pri[i].push_back(y);
            if(f&1) ty[i].push_back(-1);
            else ty[i].push_back(1);
        }
    }
}
int val[maxn],ans[maxn];
int ch[maxn][70];
int dfs(int u,int f){
    int su = 0 ;
    int va = val[u];
    for(int i = 0;i < pri[va].size();i++)
        ch[u][i] = num[pri[va][i]];
    for(int i = 0;i < head[u].size(); i++){
        int v = head[u][i];
        if(v == f) continue;
        su += dfs(v,u);
    }
    ans[u] = su;
    for(int i = 0;i < pri[va].size(); i++){
        ans[u] += num[pri[va][i]]-ch[u][i];
    }
    for(int i = 0;i < pri[va].size(); i++){
        num[pri[va][i]]+=ty[va][i];
    }
    if(va == 1) ans[u]++;
    return su+1;
}


int main(){
    int tt=1,n,u,v;
    init();
    while(scanf("%d",&n)!=EOF){
        for(int i = 1;i <= n; i++)
            head[i].clear();
        for(int i = 1; i < n ;i++){
            scanf("%d%d",&u,&v);
            head[u].push_back(v);
            head[v].push_back(u);
        }
        memset(num,0,sizeof(num));
        for(int i = 1;i <= n; i++)
            scanf("%d",&val[i]);
        dfs(1,0);
        printf("Case #%d:",tt++);
        for(int i = 1;i <= n; i++)
            printf(" %d",ans[i]);
        printf("
");
    }
    return 0;
}