小V和gcd树 带修主席树+树剖trick

(Updated: )
(10 mins to read)

题意

给定一颗无根树，点有点权$a_i$​，边有边权$\gcd(a_i, a_j)$,要求支持两种操作：

  • 修改一个点的点权，相应边权也会更改
  • 询问u->v路径上边权<=k的数量

做法

因为修改某个点的点权，同时会修改其所有出边，直观的想法是考虑bfs树，然后转化为区间修改，但是每个儿子的修改是不同的，区间每个数对x取gcd（做不了）下面就需要一种树剖的trick，每次修改的时候，我们只修改父亲和重儿子的信息，而在询问的时候，对于一整条重链，可以保证信息是正确的，而每次跳到链顶，再修改一下该点（轻儿子）与父亲的信息即可，这样就转化为简单的单点修改了。考虑本题，可以将边权下放到深度大的点上，套用上述做法即可，而区间询问<=k的数量就用带修主席树维护。

流程

modify:upd: u->fa[u] son[u]->uqueryask: u->top[u] upd: top[u]->fa[top[u]]u = fa[top[u]]ask: u->v(是重链)注意本题是把边权下放到了点权，所以u这个点的值应该去掉，所以询问的是dfn[u]+1->dfn[v]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e4 + 5, M = 1e6 + 5, up = 1e6;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, q, a[N], b[N];
vector<int> G[N];
int sz[N], top[N], son[N], dep[N], fa[N], dfn[N], idfn[N], tot;
void dfs1(int u, int f)
{
  dep[u] = dep[f] + 1; fa[u] = f;
  sz[u] = 1;
  for(int v : G[u])
  {
    if(v!=f)
    {
      dfs1(v, u);
      sz[u] += sz[v];
      if(sz[v]>sz[son[u]]) son[u] = v;
    }
  }
}
void dfs2(int u, int t)
{
  top[u] = t;
  dfn[u] = ++tot;
  idfn[tot] = u;
  if(!son[u]) return;
  dfs2(son[u], t);
  for(int v : G[u])
    if(v!=son[u]&&v!=fa[u]) dfs2(v, v);
}
namespace PSegTree
{
  #define ls(x) t[x].l
  #define rs(x) t[x].r
  int rt[N], tot;
  int lrt[N], rrt[N], lc, rc;
  struct node
  {
    int l, r, cnt;
  }t[M*32];
  void insert(int &p, int l, int r, int x, int v)
  {
    if(!p) p = ++tot;
    t[p].cnt += v;
    if(l==r) return;
    int mid = (l+r) >> 1;
    if(x<=mid) insert(ls(p), l, mid, x, v);
    else insert(rs(p), mid+1, r, x, v);
  }
  int ask(int l, int r, int k)
  {
    if(l==r)
    {
      if(l>k) return 0;
      int cnt = 0;
      for(int i=1; i<=lc; i++) cnt -= t[lrt[i]].cnt;
      for(int i=1; i<=rc; i++) cnt += t[rrt[i]].cnt;
      return cnt;
    }
    int mid = (l+r) >> 1;
    if(k<=mid)
    {
      for(int i=1; i<=lc; i++) lrt[i] = ls(lrt[i]);
      for(int i=1; i<=rc; i++) rrt[i] = ls(rrt[i]);
      return ask(l, mid, k);
    }
    else
    {
      int lcnt = 0;
      for(int i=1; i<=lc; i++) lcnt -= t[ls(lrt[i])].cnt;
      for(int i=1; i<=rc; i++) lcnt += t[ls(rrt[i])].cnt;
      for(int i=1; i<=lc; i++) lrt[i] = rs(lrt[i]);
      for(int i=1; i<=rc; i++) rrt[i] = rs(rrt[i]);
      return lcnt + ask(mid+1, r, k);
    }
  }
  #undef ls
  #undef rs
}
using namespace PSegTree;
void upd(int x, int val, int v)
{
  for(int i=x; i<=n; i+=(i&-i)) insert(rt[i], 1, up, val, v);
}
int query(int l, int r, int k)
{
  lc = 0, rc = 0;
  for(int i=l-1; i>0; i-=(i&-i)) lrt[++lc] = rt[i];
  for(int i=r; i>0; i-=(i&-i)) rrt[++rc] = rt[i];
  return ask(1, up, k);
}
int queryt(int x, int y, int k)
{
  int ans = 0;
  while(top[x]!=top[y])
  {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    int tmp = top[x];
    if(fa[tmp]&&b[tmp]!=__gcd(a[tmp], a[fa[tmp]]))
    {
      upd(dfn[tmp], b[tmp], -1);
      upd(dfn[tmp], b[tmp]=__gcd(a[tmp], a[fa[tmp]]), 1);
    }
    ans += query(dfn[top[x]], dfn[x], k);
    x = fa[top[x]];
  }
  if(dep[x]>dep[y]) swap(x,y);
  if(x!=y) ans += query(dfn[x]+1, dfn[y], k);
  return ans;
}
int main()
{
  scanf("%d%d", &n, &q);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  for(int i=1; i<n; i++)
  {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].pb(v); G[v].pb(u);
  }
  dfs1(1, 0); dfs2(1, 1);
  for(int u=2; u<=n; u++)
    upd(dfn[u], b[u]=__gcd(a[u], a[fa[u]]), 1);
  for(int i=1; i<=q; i++)
  {
    int op;
    scanf("%d", &op);
    if(op==1)
    {
      int u, x;
      scanf("%d%d", &u, &x);
      if(fa[u])
      {
        upd(dfn[u], b[u], -1);
        upd(dfn[u], b[u]=__gcd(x, a[fa[u]]), 1);
      }
      if(son[u])
      {
        upd(dfn[son[u]], b[son[u]], -1);
        upd(dfn[son[u]], b[son[u]]=__gcd(x, a[son[u]]), 1);
      }
      a[u] = x;
    }
    else
    {
      int u, v, k;
      scanf("%d%d%d", &u, &v, &k);
      printf("%d\n", queryt(u, v, k));
    }
  }
  return 0;
}