C++14(g++5.4) 解法, 执行用时: 1211ms, 内存消耗: 2920K, 提交时间: 2020-05-17 00:20:36

#include<bits/stdc++.h>
using namespace std;
const int maxn=20010;
vector<int>G[maxn];
int a[maxn],fa[maxn],dep[maxn],w[maxn],m;
void dfs(int u)
{
    for(int v:G[u]){
        if(v==fa[u]) continue;
        fa[v]=u;
        w[v]=__gcd(a[u],a[v]);
        dep[v]=dep[u]+1;
        dfs(v);
    }
    return;
}
int query(int u,int v,int k)
{
    int ans=0;
    while(u!=v){
        if(dep[v]>dep[u]) swap(u,v);
        int tmp=G[fa[u]].size()<m?w[u]:__gcd(a[fa[u]],a[u]);
        ans+=tmp<=k;
        u=fa[u];
    }
    return ans;
}
int main()
{
    int n,q,u,v,op,k,x;
    scanf("%d%d",&n,&q);
    m=sqrt(n);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1);
    while(q--){
        scanf("%d%d",&op,&u);
        if(op==1){
            scanf("%d",&x);
            if(a[u]==x) continue;
            a[u]=x;
            w[u]=__gcd(a[fa[u]],x);
            if(G[u].size()>=m) continue;
            for(int v:G[u]){
                if(v==fa[u]) continue;
                w[v]=__gcd(a[v],x);
            }
        }
        else{
            scanf("%d%d",&v,&k);
            printf("%d\n",query(u,v,k));
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1141ms, 内存消耗: 2404K, 提交时间: 2020-05-15 19:29:21

#include<bits/stdc++.h>
using namespace std;
const int N=40005;
int ne[N],fa[N],in[N],tot,out[N],fi[N],zz[N],n,m,a[N],x,y,opt,z,vis[N];
int pd(int x,int y){
	return in[x]<=in[y]&&out[x]>=out[y];
}
void dfs(int x,int y){
	fa[x]=y;in[x]=++tot;
	for (int i=fi[x];i;i=ne[i])
		if (zz[i]!=y)dfs(zz[i],x);
	out[x]=++tot;
}
void jb(int x,int y){
	ne[++tot]=fi[x];
	fi[x]=tot;
	zz[tot]=y;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		jb(x,y);jb(y,x);
	}
	tot=1;
	dfs(1,0);
	while (m--){
		scanf("%d",&opt);
		if (opt==1){
			scanf("%d",&x);
			scanf("%d",&a[x]);
			for (int i=fi[x];i;i=ne[i])
				if (zz[i]!=fa[x])vis[zz[i]]=0;
			vis[x]=0;
		}
		else {
			scanf("%d%d%d",&x,&y,&z);
			int ans=0;
			while (!pd(x,y)){
				if (!vis[x])vis[x]=__gcd(a[x],a[fa[x]]);
				ans+=vis[x]<=z;
				x=fa[x];
			}
			swap(x,y);
			while (x!=y){
				if (!vis[x])vis[x]=__gcd(a[x],a[fa[x]]);
				ans+=vis[x]<=z;
				x=fa[x];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}