HDU5799 This world need more Zhu 树上莫队

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

This world need more Zhu

Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65536/262144 K (Java/Others)

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\le T\le 10,1\le n\le 100000,1\le m\le 100000,1\le op\le 2,1\le u,v\le n,1\le a,b\le n,1\leq A[i] \leq 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

Author

UESTC

Source

题意:

给定一颗N个点的树,每个点有一个点权。Q次询问,询问子树u中,出现次数为a的树的所有数的和和出现次数为b的所有数的和的GCD,或者是询问在简单路径u到v上,出现次数为a的树的所有数的和和出现次数为b的所有数的和的GCD。

题解:

对于两种不同的询问,可以分开处理。

对于子树询问,可以采取DFS序列和普通莫队的方式来处理,按照询问子树的根的DFS序列分块,块内按照子树内DFS序的最大值排序即可。

对于树上路径的询问,可以使用树上莫队来处理。按照起点的DFS序分块,块内按照v点的DFS序排序。相邻的询问之间的转移,暴力在树上跑就行了,假设要从L点移动到L'点,其实是将从L到L'路径上所有点是否在维护区间的这个状态反转。当时我们会发现,这样会使其中某一个点的状态出现错误,我们需要找到这个点,将其反转回来,我们把这个点叫做cross点。通过画图观察可以发现,如果L'点在维护区间内(将L移动到L'意味着缩短维护的区间),那么这cross点就是L'点。对于其它的情况,可以发现,这个cross点都位于维护区间中,且处于维护和未维护的交界处。那么这个cross点就可以在暴力移动的过程中找到。