7,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973};int n, q, ans[N], deep[N]; vector
G[N], V[N]; //V[i]是i点的所有质因子, G[i]是图, P[u]和D[u]是有u这个质因子的点 map
>P; void dfs(int u, int f, int dep){ ans[u] = -1; deep[u] = dep; for(int i = (int)V[u].size()-1; i >= 0; i--){ int v = V[u][i]; if(P[v].size()==0){P[v].push_back(u);continue;} if(ans[u] == -1 || deep[ans[u]]
= 0; i--) if(G[u][i]!=f) dfs(G[u][i], u, dep+1); for(int i = (int)V[u].size()-1; i >= 0; i--){ int v = V[u][i]; P[v].erase(P[v].end()-1); } } void fenjie(int u, int v){ V[u].clear(); for(int j = 0; prime[j]*prime[j] <= v; j++) if(v%prime[j]==0) { V[u].push_back(prime[j]); while(v % prime[j]==0) v /= prime[j]; } if(v != 1) V[u].push_back(v); } void input(){ for(int v, i = 1; i <= n; i++){ scanf("%d",&v); G[i].clear(); fenjie(i, v); } for(int u, v, i = 1; i < n; i++){ scanf("%d %d",&u,&v); G[u].push_back(v); G[v].push_back(u); } } int main(){ int u, v, op; while(~scanf("%d %d", &n,&q)){ input(); dfs(1, -1, 0); while(q--){ scanf("%d %d",&op,&u); if(op==1) printf("%d\n",ans[u]); else { scanf("%d",&v); fenjie(u, v); dfs(1, -1, 0); } } } return 0; }
|