CF 제목 모음 PART 7 #264 div 2 E

[원제]
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 < k. If there are several possible vertices ui 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.
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 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

output

-1
1
2
-1
1

Note
gcd(x, y) is greatest common divisor of two integers x and y.
[분석] 이 문제는 현장 경기를 하는 것이다.A할 수 있었는데 너무 떨렸어요.
수정 조작을 시작한 지 50회밖에 안 됐는데 시간도 느슨하니 정말 시원하다!매번 이 나무를 폭력적으로 재구성해서 모든 질인자에 대해 최우수치를 기록할 수 있을 것으로 추정된다.
우선 매번 sqrt의 효율이 한 수의 인자를 매거할 수 없으면 우리는 매 수의 모든 질인자를 미리 처리할 수 있다.(사실 더 공간을 절약할 수 있는)
남은 문제는: 왜냐하면 나는 dfs를 사용하기 때문에 어떻게 어떤 하위 나무의 정보를 검색한 후에 삭제합니까? 사실 테두리 표와 유사한 사고방식을 사용할 수도 있지만 번거롭다==
【코드】

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 100005
#define S 2000005
#define push push_back
#define pop pop_back
using 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;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;i<fac[P].size();i++)
  {
    int go=fac[P][i],temp=f[go].size();
    if (temp&&deep[f[go][temp-1]]>deep[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[P].size();i++)
    f[fac[P][i]].pop();
}
inline void get_deep(int k,int fa)
{
  for (int i=end[k];i;i=a[i].next)
    if (a[i].go!=fa) deep[a[i].go]=deep[k]+1,get_deep(a[i].go,k);
}
int main()
{
  scanf("%d%d",&n,&Q);
  for (i=1;i<=n;i++)
    scanf("%d",&data[i]);
  for (i=1;i<n;i++)
    scanf("%d%d",&x,&y),add(x,y),add(y,x);
  init();deep[0]=-1;get_deep(1,0);
  memset(ans,0,sizeof(ans));dfs(1,0);
  while (Q--)
  {
    scanf("%d%d",&opt,&x);
    if (opt==1) {printf("%d
",ans[x]?ans[x]:-1);continue;}
    memset(ans,0,sizeof(ans));
    scanf("%d",&y);data[x]=y;dfs(1,0);
  }
  return 0;
}