[CF 463E] Caisa and Tree

作法：

首先因為修改操作至多$50$次，所以可以直接把他當成沒有修改，在有修改時就直接砍掉重建就好了。對於一個節點$x$來說，假設他的質因數為$p_1,...,p_r$，那麼對於$x$子樹裡的所有點來說，如果某個點$y$的值有$p_1,...,p_r$中任意一個質因數，那麼就可以用$x$去更新$y$的答案，並且$y$的答案要取深度最深的點。因此就可以想到，對這棵樹DFS，假設當前點是$u$，那麼對每個質因數都維護一個數，代表如果之後遇到的點的值有這個質因數的話，就可以用他來更新答案，不難在DFS時更新和回溯那些值，所以就可以$O(1)$回答詢問了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,MAX=2000000+10 ;
 
bool vis[MAX] ;
int pr[MAX] ;
void prime()
{
    for(int i=2;i*i<MAX;i++) if(!vis[i])
        for(int j=i*i;j<MAX;j+=i) vis[j]=1 , pr[j]=i ;
    for(int i=2;i<MAX;i++) if(!vis[i])
        pr[i]=i ;
}
 
vector<int> v[maxn] ;
int a[maxn] ;
int ans[maxn],now[MAX],dep[maxn] ;
void dfs(int x,int f,int de=1)
{
    dep[x]=de ;
    int di[7],tmp[7],dcnt=0 ;
    for(int i=a[x];i!=1;)
    {
        di[dcnt++]=pr[i] ;
        int j=i ;
        while(j%pr[i]==0) j/=pr[i] ;
        i=j ;
    }
 
    for(int i=0;i<dcnt;i++)
    {
        if(dep[now[di[i]]]>dep[ans[x]]) ans[x]=now[di[i]] ;
        tmp[i]=now[di[i]] , now[di[i]]=x ;
    }
    for(auto i : v[x]) if(i!=f) dfs(i,x,de+1) ;
    for(int i=0;i<dcnt;i++) now[di[i]]=tmp[i] ;
}
 
main()
{
    prime() ;
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    dfs(1,1) ;
    while(Q--)
    {
        int t ; scanf("%d",&t) ;
        if(t==2)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            a[x]=y ; memset(ans,0,sizeof(ans)) ;
            dfs(1,1) ;
        }
        else
        {
            int x ; scanf("%d",&x) ;
            printf("%d\n",ans[x]==0?-1:ans[x]) ;
        }
    }
}