木鎖断分−点の分治(鎖の点の個数kの点対数)
7659 ワード
hdu4760
Cube number on a tree
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 878 Accepted Submission(s): 162
Problem Description
The country Tom living in is famous for traveling. Every year, many tourists from all over the world have interests in traveling there.
There are n provinces in the country. According to the experiences from the tourists came before, every province has its own preference value. A route’s preference value from one province to another is defined as the product of all the preference value of the provinces on the route. It’s guaranteed that for each two provinces in the country there is a unique route from one to another without passing any province twice or more.
Tom is a boy crazy about cube number. A cube number is a positive integer whose cube root is also an integer. He is planning to travel from a province to another in the summer vacation and he will only choose the route with the cube number preference value. Now he want to know the number of routes that satisfy his strange requirement.
Input
The input contains several test cases, terminated by EOF.
Each case begins with a number n ( 1 ≤ n ≤ 50000), the number of the provinces.
The second line begins with a number K (1 ≤ K ≤ 30), and K difference prime numbers follow. It’s guaranteed that all the preference number can be represented by the product of some of this K numbers(a number can appear multiple times).
The third line consists of n integer numbers, the ith number indicating the preference value P
i(0 ≤ P
i ≤ 10
15) of the i-th province.
Then n - 1 lines follow. Each line consists of two integers x, y, indicating there is a road connecting province x and province y.
Output
For each test case, print a number indicating the number of routes that satisfy the requirement.
Sample Input
Sample Output
タイトル:
1本の木の形の図を与えて、すべての頂点はすべて重みの値があって、この重みの値のすべての因子はすべて与えたk個の素数の中の数字で、つまりすべての重みの値はすべて与えた素数の乗算が得られて、どれだけの観光ルートが存在するかを聞いて、すべての重みの値を乗算した後に1つの立方数(例えば1,8,27......)を与えた数はint 64の範囲内なので、直接加算比較はint 64の範囲を超えるため、与えられた素因数の性質を巧みに運用し、総積が1つの立方数であれば、その立方数の素因数の個数は必ず3の倍数であるため、指数べき乗を3進数に変換して貯蔵することができ、例えば2500の因子は2つ、0つ、3つ、4つの5があり、各数字に対して3を余り取った後に発生した3進制の表現法は201で、対応する10進法は2*3^2+0+1*3^0=19である.だから乗算の問題は三進数加算の問題に変換され、その後は木の分治の問題になる.
まず、1つのサブツリーについて、すべての子供とそのルートノード(ルートノードを含む)とのチェーンの3進数の和を求め、この3進数が0であれば条件を満たし、次に0でない3進数について、対立面(対立面0-0であれば0ではない3進数)が存在するかどうかを検索し、存在する場合も立ルートノードにまたがる条件を満たすチェーンである
具体的な過程:1つのルートノードに対して、k人の息子を加えて、それから各息子に対して深く探して、その息子とルートノードを通るすべてのチェーンを見つけて、条件を満たす個数を統計して、ついでにその息子のサブツリーのすべてのノードがルートノードを含まないチェーンを記録して、num[a]=bで記録して、つまり3進数aの個数はb個があって、これらの数値は次の息子の子の木を検索する際の対立面として、そのルートノードのすべての息子の子の木を検索した後にnum配列を空にして、以上の子の木の遍歴過程を繰り返して、最後に各子の木の統計結果を加算して答えです.
最後に、ある点自体の重み値が立方数であるかどうかを統計することを忘れないでください.
プログラム:
Cube number on a tree
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 878 Accepted Submission(s): 162
Problem Description
The country Tom living in is famous for traveling. Every year, many tourists from all over the world have interests in traveling there.
There are n provinces in the country. According to the experiences from the tourists came before, every province has its own preference value. A route’s preference value from one province to another is defined as the product of all the preference value of the provinces on the route. It’s guaranteed that for each two provinces in the country there is a unique route from one to another without passing any province twice or more.
Tom is a boy crazy about cube number. A cube number is a positive integer whose cube root is also an integer. He is planning to travel from a province to another in the summer vacation and he will only choose the route with the cube number preference value. Now he want to know the number of routes that satisfy his strange requirement.
Input
The input contains several test cases, terminated by EOF.
Each case begins with a number n ( 1 ≤ n ≤ 50000), the number of the provinces.
The second line begins with a number K (1 ≤ K ≤ 30), and K difference prime numbers follow. It’s guaranteed that all the preference number can be represented by the product of some of this K numbers(a number can appear multiple times).
The third line consists of n integer numbers, the ith number indicating the preference value P
i(0 ≤ P
i ≤ 10
15) of the i-th province.
Then n - 1 lines follow. Each line consists of two integers x, y, indicating there is a road connecting province x and province y.
Output
For each test case, print a number indicating the number of routes that satisfy the requirement.
Sample Input
5
3 2 3 5
2500 200 9 270000 27
4 2
3 5
2 5
4 1
Sample Output
1
タイトル:
1本の木の形の図を与えて、すべての頂点はすべて重みの値があって、この重みの値のすべての因子はすべて与えたk個の素数の中の数字で、つまりすべての重みの値はすべて与えた素数の乗算が得られて、どれだけの観光ルートが存在するかを聞いて、すべての重みの値を乗算した後に1つの立方数(例えば1,8,27......)を与えた数はint 64の範囲内なので、直接加算比較はint 64の範囲を超えるため、与えられた素因数の性質を巧みに運用し、総積が1つの立方数であれば、その立方数の素因数の個数は必ず3の倍数であるため、指数べき乗を3進数に変換して貯蔵することができ、例えば2500の因子は2つ、0つ、3つ、4つの5があり、各数字に対して3を余り取った後に発生した3進制の表現法は201で、対応する10進法は2*3^2+0+1*3^0=19である.だから乗算の問題は三進数加算の問題に変換され、その後は木の分治の問題になる.
まず、1つのサブツリーについて、すべての子供とそのルートノード(ルートノードを含む)とのチェーンの3進数の和を求め、この3進数が0であれば条件を満たし、次に0でない3進数について、対立面(対立面0-0であれば0ではない3進数)が存在するかどうかを検索し、存在する場合も立ルートノードにまたがる条件を満たすチェーンである
具体的な過程:1つのルートノードに対して、k人の息子を加えて、それから各息子に対して深く探して、その息子とルートノードを通るすべてのチェーンを見つけて、条件を満たす個数を統計して、ついでにその息子のサブツリーのすべてのノードがルートノードを含まないチェーンを記録して、num[a]=bで記録して、つまり3進数aの個数はb個があって、これらの数値は次の息子の子の木を検索する際の対立面として、そのルートノードのすべての息子の子の木を検索した後にnum配列を空にして、以上の子の木の遍歴過程を繰り返して、最後に各子の木の統計結果を加算して答えです.
最後に、ある点自体の重み値が立方数であるかどうかを統計することを忘れないでください.
プログラム:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include"stdio.h"
#include"string.h"
#include"iostream"
#include"map"
#include"string"
#include"queue"
#include"stdlib.h"
#include"math.h"
#define M 50009
#define eps 1e-10
#define inf 99999999
#define mod 1000000000
using namespace std;
struct node
{
int u,v,next;
}edge[M*3];
int t,head[M],use[M],son[M],limit[M],k,MN,ID,cnt,ans;
__int64 prime[33],value[M],cube[33],dis[M];
void init()
{
t=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
edge[t].u=u;
edge[t].v=v;
edge[t].next=head[u];
head[u]=t++;
}
__int64 Add(__int64 m,__int64 n)
{
int a[33],b[33],i,j;
for(i=0;i<k;i++)
a[i]=b[i]=0;
i=0;
while(m)
{
a[i++]=m%3;
m/=3;
}
j=0;
while(n)
{
b[j++]=n%3;
n/=3;
}
__int64 ss=0;
for(i=0;i<k;i++)
ss+=cube[i]*((a[i]+b[i])%3);
return ss;
}//
__int64 down(__int64 m,__int64 n)
{
int a[33],b[33],i,j;
for(i=0;i<k;i++)
a[i]=b[i]=0;
i=0;
while(m)
{
a[i++]=m%3;
m/=3;
}
j=0;
while(n)
{
b[j++]=n%3;
n/=3;
}
__int64 ss=0;
for(i=0;i<k;i++)
ss+=cube[i]*((3+a[i]-b[i])%3);
return ss;
}//
void dfs_size(int u,int f)
{
son[u]=1;
limit[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(f!=v&&!use[v])
{
dfs_size(v,u);
son[u]+=son[v];
limit[u]=max(limit[u],son[v]);
}
}
}
void dfs_root(int root,int u,int f)
{
if(son[root]-son[u]>limit[u])
limit[u]=son[root]-son[u];
if(MN>limit[u])
{
MN=limit[u];
ID=u;
}
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(f!=v&&!use[v])
{
dfs_root(root,v,u);
}
}
}//
void dfs_dis(int u,int f,__int64 id)
{
dis[cnt++]=id;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v!=f&&!use[v])
{
dfs_dis(v,u,Add(id,value[v]));
}
}
}//
__int64 cal(int u,int f)//
{
int sum=0;
map<__int64,int>mp;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v!=f&&!use[v])
{
cnt=0;
dfs_dis(v,u,Add(value[ID],value[v]));
for(int j=0;j<cnt;j++)
{
if(dis[j]==0)
sum++;
__int64 op=down(0,dis[j]);
sum+=mp[op];
}
for(int j=0;j<cnt;j++)
{
mp[down(dis[j],value[ID])]++;
}
}
}
return sum;
}
void dfs_ans(int root,int u,int f)//
{
dfs_size(u,f);
MN=inf;
dfs_root(root,u,f);
ans+=cal(ID,ID);
use[ID]=1;
for(int i=head[ID];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v])
{
dfs_ans(v,v,v);
}
}
}
void slove(int n)
{
memset(use,0,sizeof(use));
ans=0;
dfs_ans(1,1,1);
for(int i=1;i<=n;i++)
if(value[i]==0)
ans++;
printf("%d
",ans);
}
int main()
{
int n,i,j;
cube[0]=1;
for(i=1;i<30;i++)
cube[i]=cube[i-1]*3;
while(scanf("%d",&n)!=-1)
{
scanf("%d",&k);
for(i=0;i<k;i++)
scanf("%I64d",&prime[i]);
for(i=1;i<=n;i++)
{
value[i]=0;
__int64 p;
scanf("%I64d",&p);
for(j=0;j<k;j++)
{
int r=0;
while(p%prime[j]==0)
{
p=p/prime[j];
r++;
r%=3;
}
value[i]+=cube[k-j-1]*(r%3);
}
}
init();
for(i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
slove(n);
}
return 0;
}