题意

有一颗 个节点的树，每个点有权值 ， 这条边的权值为 。有 次操作：

  • 将节点 的值改为
  • 询问 到 的路径上有多少条边边权不超过

其中，，。

分析

首先看到这题时限 ，果断上 O(1)gcd + 暴力，复杂度 ，结果没卡过去。。。
不过为什么其他人的 做法都能过啊，我的就不能过QAQ
下面的解法学习自 CYJian大佬的博客。Orz
先以 为根节点，进行树链剖分。（如果你不会树剖，可以先去看看 这道模板题
然后每次修改节点 的值，先只对重链上的边进行修改。
这样子就保证了重链上的边都是正确值。
然后在跳链时，再更新重链之间的连接边（轻链）的边权即可。
修改边权 + 查询不超过 的边的个数可以使用动态修改的主席树。（如果你不会动态修改主席树，可以先去看看这道模板题，我也是现学的
复杂度的话，由于每次只会跳 次，每次跳更新和求和的时间复杂度都是 。
所以总的复杂度是 。
最关键的点是每次只修改重链，遇到轻链再修改轻链，这样做的原因大概是树剖在跳的过程中是一直在沿着重链往上跳，最多会遇到 条轻链，不知道是不是套路，不过感觉还是挺巧妙的QAQ。

代码如下

#include <bits/stdc++.h>
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
#define N 20005
using namespace std;
typedef long long LL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
struct node{
    int a, b, c, n;
}d[N * 2];
int n, dep[N], re[N], siz[N], son[N], fa[N], top[N], h[N], v[N], w[N], dfn[N], dft, cnt, maxn = 1000000;
int cur1, cur2, L[35], R[35], ret, root[N], sum[N * 400], lch[N * 400], rch[N * 400];
void update(int l, int r, int &rt, int p, int c){
    if(!rt) rt = ++ret;
    sum[rt] += c;
    if(l == r) return;
    int m = l + r >> 1;
    if(p <= m) update(lson, p, c);
    else update(rson, p, c);
}
int query(int l, int r, int k){
    int i, m = l + r >> 1;
    LL siz = 0;
    if(l == r){
        for(i = 1; i <= cur1; i++) siz -= sum[L[i]];
        for(i = 1; i <= cur2; i++) siz += sum[R[i]];
        return siz;
    }
    if(k <= m){
        for(i = 1; i <= cur1; i++) L[i] = lch[L[i]];
        for(i = 1; i <= cur2; i++) R[i] = lch[R[i]];
        return query(l, m, k);
    }
    else{
        for(i = 1; i <= cur1; i++) siz -= sum[lch[L[i]]], L[i] = rch[L[i]];
        for(i = 1; i <= cur2; i++) siz += sum[lch[R[i]]], R[i] = rch[R[i]];
        return siz + query(m + 1, r, k);
    }
}
int gsum(int l, int r, int k){
    cur1 = cur2 = 0;
    for(int i = l - 1; i > 0; i -= i & -i) L[++cur1] = root[i];
    for(int i = r; i > 0; i -= i & -i) R[++cur2] = root[i];
    return query(0, maxn, k);
}
void add(int x, int v, int c){
    for(int i = x; i <= n; i += i & -i) update(0, maxn, root[i], v, c);
}
void cr(int a, int    b){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs1(int a){
    int i, b;
    siz[a] = 1;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b == fa[a]) continue;
        fa[b] = a;
        dep[b] = dep[a] + 1;
        w[b] = __gcd(v[b], v[a]);
        dfs1(b);
        siz[a] += siz[b];
        if(siz[b] >= siz[son[a]]) son[a] = b;
    }
}
void dfs2(int a, int f){
    int i, b;
    top[a] = f; dfn[a] = ++dft;
    if(son[a]) dfs2(son[a], f);
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b != fa[a] && b != son[a]) dfs2(b, b);
    }
}
void modify(int a){
    if(son[a]){
        int b = son[a];
        add(dfn[b], w[b], -1);
        w[b] = __gcd(v[a], v[b]);
        add(dfn[b], w[b], 1);
    }
    if(fa[a]){
        int b = fa[a];
        add(dfn[a], w[a], -1);
        w[a] = __gcd(v[a], v[b]);
        add(dfn[a], w[a], 1);
    }
}
int find(int a, int b, int c){
    int s = 0, f1 = top[a], f2 = top[b];
    while(f1 != f2){
        if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
        add(dfn[f1], w[f1], -1);
        w[f1] = __gcd(v[f1], v[fa[f1]]);
        add(dfn[f1], w[f1], 1);
        s += gsum(dfn[f1], dfn[a], c);
        a = fa[f1], f1 = top[a];
    }
    if(dep[a] > dep[b]) swap(a, b);
    if(a != b) s += gsum(dfn[a] + 1, dfn[b], c);
    return s;
}
int main(){
    int i, j, m, o, a, b, c;
    n = read(); m = read();
    for(i = 1; i <= n; i++) v[i] = read();
    for(i = 1; i < n; i++){
        a = read(); b = read();
        cr(a, b); cr(b, a);
    }
    dfs1(1);
    dfs2(1, 1);
    for(i = 1; i <= n; i++) add(dfn[i], w[i], 1);
    for(i = 1; i <= m; i++){
        o = read(); a = read(); b = read();
        if(o == 1){
            v[a] = b;
            modify(a);
        }
        else{
            c = read();
            printf("%d\n", find(a, b, c));
        }
    }
    return 0;
}