主题

主题

 
   

This world need more Zhu

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5799

Problem Description

As we all know,Zhu is the most powerful man.He has the infinite power to protest the world.We need more men like Zhu!

In Duoladuo,this place is like a tree.There are n points and n-1 edges.And the root is 1.Each point can reach other points.Each point has a value a[i] named Zhu power.

Liao is a curious baby,he has m questions to ask Zhu.But now Zhu is busy,he wants you to help him answer Liao's questions.

Liao's question will be like"op u v a b".

if op is "1",the u is equal to v.Liao wants to know the GCD of the sum of numbers thats appears a times and the sum of numbers that appears b times in subtree u.

if op is "2",Liao wants to know the GCD of the sum of numbers thats appears a times and the sum of numbers that appears b times on the path from u to v.

GCD is greatest common divisor.

notice:we can know GCD(x,0) = x.

Input

In the first line contains a single positive integer T, indicating number of test case.

In the second line there are two numbers n,m.n is the size of Duoladuo.m is the number of Liao's questions.

The next line contains n integers A1, A2, ...AN, means the value of i point.

In the next n-1 line contains tow numbers u,v.It means there is a edge between point u and point v.

The next m lines will be the Liao's question: 

1 u v a b.

2 u v a b.

1≤T≤10,1≤n≤100000,1≤m≤100000,1≤op≤2,1≤u,v≤n,1≤a,b≤n,1≤A[i]≤1000000000.

Output

For each case, output Case #i:. (ii is the number of the test case, from 1 to T). 

Then, you need to output the answer for every Liao's questions.

Sample Input

1

5 5

1 2 4 1 2

1 2

2 3

3 4

4 5

1 1 1 1 1

1 1 1 1 2

2 1 5 1 1

2 1 5 1 2

2 1 1 2 2

Sample Output

Case #1:

4

1

4

1

0

Hint

The query1: gcd(4,4) = 4

The query2: gcd(4,1+2)=1

The query3: gcd(4,4) = 4

The query4: gcd(4,1+2) = 1

The query5: gcd(0,0) = 0


题目大意:

给出一棵大小为n的树,,点有点权。给出m个操作:

  1. 查询u的子树中,出现了a次的点权的和Suma 与出现了b次的点权的和Sumb 的Gcd。

  2. 查询(u,v)的路径中,出现了a次的点权的和Suma 与出现了b次的点权的和Sumb 的Gcd。


个人解法:

刚开始看错题目,以为是出现了a次的点权的个数……大雾……好在权值和也比较好维护……

刚开始一看到子树查询+树链查询,就想树链剖分……然后想了一会发现不会做……

正在感叹自己夕阳红选手,写不动数据结构的时候,回忆起,在codeforces某题中用到过一次桶维护桶的奇妙方法,搭配莫队可以查询出现次数等于/大于/小于k的数字的个数。

然后放到这题上,就是换成树上莫队了。

对于子树的询问,做出DFS序,转换为区间莫队。对于树链的询问,做树链莫队。


代码如下:

https://code.csdn.net/snippets/2304946

 
 
评论