Codeforces Round #264 (Div. 2) E. Caisa and Tree Operation violence on the tree_html/css_WEB-ITnose

http://codeforces.com/contest/463/problem/E

Given a tree with a total number of nodes n, each node has a value, perform q Operations, each operation has two options:
1. Query each node on the path between node v and root, and find the distance that satisfies the condition gcd(val[i], val[v]) > 1 vThe index of the nearest node.

2. Change the value of node v to w.

The violence is over!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include < map>
#include <cassert>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf(" %d%d",&x,&y)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
const int maxn = 400005;
struct edge{
int next,to;
}e[maxn];
int head[maxn],n,q,w[maxn],cntn,f[maxn];
void add (int u,int v)
{
e[cntn] = (edge){head[u],v};
head[u] = cntn ;
e[cntn] = ( edge){head[v],u};
head[v] = cntn ;
}
int gcd(int x,int y)
{
return y == 0 ? x:gcd(y,x%y);
}
void dfs(int u,int fa)
{
f[u] = fa;
for(int i = head [u];i != -1;i = e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs( v,u);
}
}
int find_gcd(int v)
{
int u = f[v];
while(u != -1){
int res = gcd(w[v],w[u]);
if(res > 1){
return u;
}
u = f[u];
}
return -1;
}
int main() {
RD2(n,q);
for(int i = 1;i <= n; i)
RD(w[i]);
int m = n - 1,u,v,ww;
memset(head,-1,sizeof(head)),clr0(f);
while(m--){
RD2(u,v);
add(u,v);
}
dfs(1,-1);
while(q- -){
RD2(u,v);
if(u == 1){
printf("%dn",find_gcd(v));
}
else{
RD(ww);
w[v] = ww;
}
}
return 0;
}