CF 题目集锦 PART 7 #264 div 2 E_html/css_WEB-ITnose

【原题】

E. Caisa and Tree

time limit per test

10 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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: u1,?u2,?...,?uk (u1?=?1; uk?=?v). You need to output such a vertex ui that gcd(value of ui,?value of v)?>?1 and i?

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.

Input

The first line contains two space-separated integers n, q (1?≤?n,?q?≤?105).

The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?2·106), where ai represent the value of node i.

Each of the next n?-?1 lines contains two integers xi and yi (1?≤?xi,?yi?≤?n; xi?≠?yi), denoting the edge of the tree between vertices xi and yi.

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·106. Note that: there are no more than 50 queries that changes the value of a vertex.

Output

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

Sample test(s)

input

4 610 8 4 31 22 33 41 11 21 31 42 1 91 4

output

-112-11

Note

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

【分析】这道题是做现场赛的。本来能A的，但是太紧张了=而且也不会用vector，边表搞的麻烦死了。

开始看到修改操作才50次、时间又松，真是爽！估计每次可以暴力重构这颗树，然后对于每个质因子记录最优值。

首先每次不能sqrt的效率枚举一个数的因子，我们可以预处理出每个数的所有质因子。（其实有更省空间的）

剩下来要解决的问题是：因为我是用dfs的，怎么把某个子树的信息在搜完后再去掉？（以免影响其他子树）HHD表示用vector一点也不虚。其实应该也可以用边表类似的思路，但是麻烦= =

【代码】

#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#define N 100005#define S 2000005#define push push_back#define pop pop_backusing namespace std;vector<int>fac[S],f[S];int data[N],ans[N],end[N],pf[S],deep[N];int C,cnt,n,Q,i,x,y,opt;struct arr{int go,next;}a[N*2];inline void add(int u,int v){a[++cnt].go=v;a[cnt].next=end[u];end[u]=cnt;}inline void init(){  int H=2000000;  for (int i=2;ideep[ans[k]]) ans[k]=f[go][temp-1];    f[go].push(k);  }  for (int i=end[k];i;i=a[i].next)    if (a[i].go!=fa)      dfs(a[i].go,k);  for (int i=0;i<fac f void get_deep k fa for i="end[k];i;i=a[i].next)" if deep main scanf init memset while return>  <p></p> </fac></int></vector></cstring></algorithm></cstdio>