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


standard input


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.


    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.


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

    Sample test(s)


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




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




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


    #include#include#include#include#define N 100005#define S 2000005#define push push_back#define pop pop_backusing namespace std;vectorfac[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;i<=H;i++)    if (!pf[i])    {      for (int j=i;j<=H;j+=i)        fac[j].push(i),pf[j]=1;    }}void dfs(int k,int fa){  int P=data[k];  for (int i=0;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