409366: GYM103492 C GCD on Tree

You are given a tree with $$$n$$$ nodes and $$$n-1$$$ edges that make all nodes connected. Each node $$$i$$$ is assigned a weight $$$a_i$$$.

Now you need to perform $$$m$$$ operations of two different types. One is to change the weight of a node. The other is to query the number of pairs $$$(x,y)$$$ $$$(1 \le x \le y \le n)$$$ in the entire tree such that the greatest common divisor of the weights of all nodes on the shortest path from node $$$x$$$ to node $$$y$$$ is $$$k$$$.

The first line contains a single integer $$$T$$$ $$$(1\le T\le 8)$$$, representing the number of test cases.

For each test case, the first line contains two integers $$$n$$$ $$$(1\le n\le 10^4)$$$ and $$$m$$$ $$$(1\le m\le 10^4)$$$, representing the number of nodes and operations respectively.

The second line contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i$$$ $$$(1\le a_i\le 10^4)$$$ represents the initial weight of node $$$i$$$.

The third line contains $$$n-1$$$ integers. The $$$i$$$-th integer $$$p_{i+1}$$$ $$$(1\le p_{i+1}\le i)$$$ represents that there's an edge between node $$$i+1$$$ and node $$$p_{i+1}$$$.

The following $$$m$$$ lines describe the operations.

• $$$\texttt{0 u c}$$$: change the weight of node $$$u$$$ $$$(1\le u\le n)$$$ to $$$c$$$ $$$(1\le c\le 10^4)$$$;
• $$$\texttt{1 k}$$$: query the number of pairs $$$(x,y)$$$ $$$(1 \le x \le y \le n)$$$ in the entire tree such that the greatest common divisor of the weights of all nodes on the shortest path from node $$$x$$$ to node $$$y$$$ is $$$k$$$ $$$(1 \le k \le 10^4)$$$.

For each query, output the answer in a single line.

2
8 6
2 1 5 6 7 2 3 4
1 2 2 4 4 1 7
1 2
0 2 2
1 2
1 5
0 7 4
1 2
3 5
1 2 3
1 1
1 1
0 1 6
1 2
1 3
1 6

3
9
1
17
4
2
2
1