?
给出一个总节点数量为n的树，每个节点有权值，进行q次操作，每次操作有两种选项： 1. 询问节点v到root之间的路径上的各个节点，求满足条件 gcd(val[i], val[v]) > 1 的 距离v最近的节点的下标。
2. 将节点v的值求改为w。
暴力居然过了！
#include #include #include #include #include #include #include #include #include #include #include #include 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(%d ,find_gcd(v)); } else{ RD(ww); w[v] = ww; } } return 0; }