牛客挑战赛 40 E 题题解

yysy，这题 连 都不要，为啥要开 啊，故意放暴力过？？？

这里是个非常弱智的做法：

随便钦定一个点为根之后，考虑将一条边的边权放在儿子节点上。

首先树剖，然后考虑修改 的点权，可以先只修改其重儿子以及其到父亲的边的边权。

然后考虑用带修主席树（树套树）维护一下区间内边权出现次数。

再然后，询问的时候跳重链，链顶都更新一下其到父亲的边权，然后更新一下带修主席树中存的东西，然后询问区间内出现次数。

然后，就是码板子的事情了。

/********************************************************************************

    Code by a weak man who named CYJian, and he hopes the code can get more points.

    Algorithm:

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
    char ch, t = 0; x = 0;
    while(!isdigit(ch = ge)) t |= ch == '-';
    while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
    x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

const int inf = 1e9;
const int mod = 998244353;
const int MAXN = 20010;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }
inline int fsp(int x, int k = mod - 2) {
    int s = 1;
    while(k) {
        if(k & 1) s = 1LL * s * x % mod;
        x = 1LL * x * x % mod, k >>= 1;
    } return s;
}

inline int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }

vector<int>to[MAXN];

int n, q, tim;
int a[MAXN];
int v[MAXN];
int fa[MAXN];
int hs[MAXN];
int si[MAXN];
int dfn[MAXN];
int dep[MAXN];
int top[MAXN];

inline void dfs1(int x, int la) {
    si[x] = 1, fa[x] = la, dep[x] = la;
    for(auto u : to[x]) {
        if(u == la) continue;
        dfs1(u, x), si[x] += si[u];
        if(si[hs[x]] < si[u]) hs[x] = u;
    }
}

inline void dfs2(int x, int la) {
    dfn[x] = ++tim;
    if(hs[x]) top[hs[x]] = top[x], dfs2(hs[x], x);
    for(auto u : to[x]) {
        if(u == la || u == hs[x]) continue;
        top[u] = u, dfs2(u, x);
    }
}

int rt[MAXN];
int A[20], ca;
int B[20], cb;

struct Segment_Tree {
#define ls(x) T[x].l
#define rs(x) T[x].r

    struct Node { int l, r, c; } T[40000000];
    int ct;

    inline void Insert(int &x, int l, int r, int p, int v) {
        if(!x) x = ++ct; T[x].c += v;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        p <= mid ? Insert(ls(x), l, mid, p, v) : Insert(rs(x), mid + 1, r, p, v);
    }

    inline int Query(int l, int r, int k) {
        if(l == r) {
            int ct = 0;
            for(int i = 0; i < ca; i++) ct -= T[A[i]].c;
            for(int i = 0; i < cb; i++) ct += T[B[i]].c;
            return ct;
        } int mid = (l + r) >> 1;
        if(k <= mid) {
            for(int i = 0; i < ca; i++) A[i] = ls(A[i]);
            for(int i = 0; i < cb; i++) B[i] = ls(B[i]);
            return Query(l, mid, k);
        } int ct = 0;
        for(int i = 0; i < ca; i++) ct -= T[ls(A[i])].c;
        for(int i = 0; i < cb; i++) ct += T[ls(B[i])].c;
        for(int i = 0; i < ca; i++) A[i] = rs(A[i]);
        for(int i = 0; i < cb; i++) B[i] = rs(B[i]);
        return Query(mid + 1, r, k) + ct;
    }

#undef ls
#undef rs
}seg;

inline void Insert(int p, int v, int k) {
    while(p <= n) seg.Insert(rt[p], 1, 1000000, v, k), p += p & -p;
}

inline int Sum(int l, int r, int k) {
    ca = 0, cb = 0, --l;
    while(l) A[ca++] = rt[l], l ^= l & -l;
    while(r) B[cb++] = rt[r], r ^= r & -r;
    return seg.Query(1, 1000000, k);
}

inline void Modify(int p, int x) {
    a[p] = x;
    if(hs[p]) {
        Insert(dfn[hs[p]], v[hs[p]], -1);
        v[hs[p]] = gcd(a[hs[p]], a[p]);
        Insert(dfn[hs[p]], v[hs[p]], 1);
    }
    if(fa[p]) {
        Insert(dfn[p], v[p], -1);
        v[p] = gcd(a[p], a[fa[p]]);
        Insert(dfn[p], v[p], 1);
    }
}

inline int Query(int u, int v, int k) {
    int res = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        int tu = top[u];
        Insert(dfn[tu], ::v[tu], -1);
        ::v[tu] = gcd(a[tu], a[fa[tu]]);
        Insert(dfn[tu], ::v[tu], 1);
        res += Sum(dfn[tu], dfn[u], k);
        u = fa[tu];
    } if(dep[u] > dep[v]) swap(u, v);
    if(u != v) res += Sum(dfn[u] + 1, dfn[v], k);
    return res;
}

int main() {
#ifdef LOCAL
    FILE("a.");
#endif

    n = ri, q = ri;

    for(int i = 1; i <= n; i++) a[i] = ri;
    for(int i = 1; i < n; i++) {
        int u = ri, v = ri;
        to[u].push_back(v);
        to[v].push_back(u);
    } dfs1(1, 0), dfs2(1, 0);
    for(int i = 2; i <= n; i++) v[i] = gcd(a[i], a[fa[i]]), Insert(dfn[i], v[i], 1);
    while(q--) {
        int op = ri, u = ri;
        if(op == 1) Modify(u, ri);
        else {
            int v = ri, k = ri;
            printf("%d\n", Query(u, v, k));
        }
    } return 0;
}