小V和gcd树

小V和gcd树

树上问题，每次询问与两点有关，可以确定应该使用树链剖分来求解了。

这个问题中涉及到边的查询，树链剖分中有一个很常用的操作就是边权下放到点权上，

但这个操作一般是对有根树而言的，当然我们虚拟号节点为跟节点也是一样的。

我们假设这棵树的根节点为号节点，然后把所有的边权下放到其对应的节点上（1号节点所代表的边权就为空了）。

对于查询操作：查找，用树链剖分在最短路上跳转遍历所有的边，然后统计答案。

对于修改操作：查找，对于每个节点，我们需要修改其与父节点的权值，其与儿子节点的权值。

但是这样只能过的测试点，所以考虑如何优化。

查询操作是无法优化了，我们只能考虑如何简化修改操作毕竟是无法通过这题的。

大致思路跟原来还是一样的，只是我们要减小查询操作的常数。

我们约定，，是节点的父节点，当且仅当的时候（作为的重儿子），我们才下放边权到上。

所以对于修改操作我们只要修改两个点了：

• 当这个点不是某条链的时，修改其与其父节点的值。
• 当这个点有重儿子时，修改其与其重儿子的值。

对于查询操作我们也要做适当的调整，在之前我们的查询操作是从到的值进行查询，

但是因为没有记录，所以我们的查询应该是从到进行查询，

然后单独算。

这样我们可以保证查询复杂度不会变差同样也是的，并且保证了修改操作时的。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 10;

int head[N], to[N << 1], nex[N << 1], cnt = 1;

int fa[N], top[N], dep[N], sz[N], son[N], rk[N], id[N], tot;

int n, m, a[N], value[N];

void add(int x, int y) {
  to[cnt] = y;
  nex[cnt] = head[x];
  head[x] = cnt++;
}

void dfs1(int rt, int f) {
  sz[rt] = 1, dep[rt] = dep[f] + 1, fa[rt] = f;
  for (int i = head[rt]; i; i = nex[i]) {
    if (to[i] == f) {
      continue;
    }
    dfs1(to[i], rt);
    sz[rt] += sz[to[i]];
    if (!son[rt] || sz[to[i]] > sz[son[rt]]) {
      son[rt] = to[i];
    }
  }
}

void dfs2(int rt, int tp) {
  rk[++tot] = rt, id[rt] = tot, top[rt] = tp;
  if (top[rt] != rt) {
    a[id[rt]] = __gcd(value[rt], value[fa[rt]]);
  }
  if (!son[rt]) {
    return ;
  }
  dfs2(son[rt], tp);
  for (int i = head[rt]; i; i = nex[i]) {
    if (to[i] == fa[rt] || to[i] == son[rt]) {
      continue;
    }
    dfs2(to[i], to[i]);
  }
}

int query(int x, int y, int k) {
  int ans = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) {
      swap(x, y);
    }
    for (int i = id[top[x]] + 1; i <= id[x]; i++) {
      ans += a[i] <= k;
    }
    if (fa[top[x]]) {
      ans += __gcd(value[top[x]], value[fa[top[x]]]) <= k;
    }
    x = fa[top[x]];
  }
  if (dep[x] > dep[y]) {
    swap(x, y);
  }
  for (int i = id[x] + 1; i <= id[y]; i++) {
    ans += a[i] <= k;
  }
  return ans;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &value[i]);
  }
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    add(x, y);
    add(y, x);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  while (m--) {
    int op, u, v, x, k;
    scanf("%d %d", &op, &u);
    if (op & 1) {
      scanf("%d", &x);
      value[u] = x;
      if (top[u] != u) {
        a[id[u]] = __gcd(value[fa[u]], value[u]);
      }
      if (son[u]) {
        a[id[son[u]]] = __gcd(value[u], value[son[u]]);
      }
    }
    else {
      scanf("%d %d", &v, &k);
      printf("%d\n", query(u, v, k));
    }
  }
  return 0;
}