Caisa and Tree

题意翻译

#### 问题描述： 给你一个根为 $1$ 的 $n$（$1\le n \le 10^5$） 个节点的树，每个点有一个点权。你需要进行 $q$（$1\le q \le 10^5$） 个操作。操作类型如下： $1.$ 输入格式形如 $1\ \ v$。 我们设从根节点 $1$ 到 节点 $v$ 的路径上的点为 $u_1,u_2,u_3,......u_k\ (u_1=1,u_k=v)$，你需要输出一个 $u_i$ 满 足 $\gcd(value\ of\ u_i,value\ of\ v)>1\ \&\ i<k$ 。如果有多个满足条件的 $u_i$，输出 $i$ 最大的那个。如果没有解输出 $-1$。 $2.$ 输入格式形如 $2\ \ v\ \ d$。把 节点 $v$ 的点权修改为 $d$。（$1\le v\le n,\ \ 1\le d\le 2\times 10^6$）。 #### 输入格式： 第一行两个正整数 $n$ 和 $q$。意义如上。 第二行 $n$ 个正整数，表示点权。（$1\le a_i\le 2\times 10^6$）。 之后的 $n-1$ 行，每行描述一条树上的边。 接下来的 $q$ 行，每行描述一个操作，格式和意义如上。 保证 $2$ 操作的数量不超过 $50$。 #### 输出格式： 对于每个 $1$ 操作，输出答案。

题目描述

Caisa is now at home and his son has a simple task for him. Given a rooted tree with $ n $ vertices, numbered from $ 1 $ to $ n $ (vertex $ 1 $ is the root). Each vertex of the tree has a value. You should answer $ q $ queries. Each query is one of the following: - Format of the query is "1 $ v $ ". Let's write out the sequence of vertices along the path from the root to vertex $ v $ : $ u_{1},u_{2},...,u_{k} $ $ (u_{1}=1; u_{k}=v) $ . You need to output such a vertex $ u_{i} $ that $ gcd(value of u_{i},value of v)&gt;1 $ and $ i&lt;k $ . If there are several possible vertices $ u_{i} $ pick the one with maximum value of $ i $ . If there is no such vertex output -1. - Format of the query is "2 $ v $ $ w $ ". You must change the value of vertex $ v $ to $ w $ . You are given all the queries, help Caisa to solve the problem.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ , $ q $ $ (1<=n,q<=10^{5}) $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=2·10^{6}) $ , where $ a_{i} $ represent the value of node $ i $ . Each of the next $ n-1 $ lines contains two integers $ x_{i} $ and $ y_{i} $ $ (1<=x_{i},y_{i}<=n; x_{i}≠y_{i}) $ , denoting the edge of the tree between vertices $ x_{i} $ and $ y_{i} $ . Each of the next $ q $ lines contains a query in the format that is given above. For each query the following inequalities hold: $ 1<=v<=n $ and $ 1<=w<=2·10^{6} $ . Note that: there are no more than $ 50 $ queries that changes the value of a vertex.

输出格式

For each query of the first type output the result of the query.

输入输出样例

输入样例 #1

4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

输出样例 #1

-1
1
2
-1
1

说明

$ gcd(x,y) $ is greatest common divisor of two integers $ x $ and $ y $ .