树链剖分专题
Posted Updated Notes26 minutes read (About 3949 words)

树链剖分专题

显然的板子题。

那么我们只需要干这样一件事情，就是按照重儿子的顺序来进行 DFS，那么这样我们就可以通过 DFS 序这样一个东西来进行子树的查询和更改，同时也可以通过跳链顶，类似 LCA 的操作，来进行路径的修改和查询。这都非常容易实现。

所以代码会长下面这样。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int n, m, root, Mod, cnt, idx;
int w[N], wl[N], val[N<<2], head[N<<1];
int dep[N], id[N], fa[N], son[N];
int lazy[N<<2], tp[N], siz[N];

struct Edge {
  int to, nxt;
} e[N<<1];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void pushup(int rt) {
  val[rt] = (val[ls] + val[rs]) % Mod;
  return ;
}

void build(int rt, int l, int r) {
  if (l==r) { val[rt] = wl[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
  lazy[ls] %= Mod, lazy[rs] %= Mod;
  val[ls] = (val[ls] + (mid-l+1) * lazy[rt]) % Mod;
  val[rs] = (val[rs] + (r-mid) * lazy[rt]) % Mod;
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) {
    val[rt] += (r-l+1) * f, val[rt] %= Mod;
    lazy[rt] += f, lazy[rt] %= Mod;
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans % Mod;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  siz[cur] = 1, fa[cur] = f;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to]>heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx, wl[idx] = w[cur];
  tp[cur] = Tp; if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==son[cur] || to==fa[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

void up(int l, int r, int f) {
  f %= Mod;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], f);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], f);
  return ;
}

int qu(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans = (ans + query(1, 1, n, id[tp[l]], id[l])) % Mod;
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = (ans + query(1, 1, n, id[l], id[r])) % Mod;
  return ans;
}

void upsub(int x, int f) { upd(1, 1, n, id[x], id[x]+siz[x]-1, f); }
int qusub(int x) { return query(1, 1, n, id[x], id[x]+siz[x]-1); }

signed main() {
  read(n), read(m);
  read(root), read(Mod);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(root, root);
  dfs2(root, 0); build(1, 1, n);
  while (m--) {
    int opt, x, y, z;
    read(opt);
    if (opt==1) {
      read(x), read(y), read(z);
      up(x, y, z);
    } else if (opt==2) {
      read(x), read(y);
      printf("%lld\n", qu(x, y) % Mod);
    } else if (opt==3) {
      read(x), read(z);
      upsub(x, z);
    } else { read(x); printf("%lld\n", qusub(x) % Mod); }
  }
  return 0;
}

更简单了，甚至不需要 lazytag。

代码如下。

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
#include <stdio.h>
#include <iostream>
#define isdigit(ch) (ch>47&&ch<58)

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch ^ '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void out(int ret) {
  if (ret<0) { ret = -ret, putchar('-'); }
  if (ret>9) out(ret/10);
  putchar(ret%10 ^ 48); return ;
}

const int N = 3e4 + 10;
int n, Q, cnt, dfn;
int w[N], v[N], head[N];

int val[N<<2], siz[N], Maxi[N<<2];
int id[N], fa[N], tp[N], son[N], dep[N];
char str[10];

int max(int x, int y) { return x>y? x:y; }
void swap(int &x, int &y) { x ^= y ^= x ^= y; }

struct Edge {
  int to, nxt;
} e[N<<1];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt;
  return ;
}

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  Maxi[rt] = max(Maxi[ls], Maxi[rs]);
  return ;
}

void build(int rt, int l, int r) {
  if (l == r) { val[rt] = Maxi[rt] = v[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void upd(int rt, int l, int r, int pos, int f) {
  if (l == r) { val[rt] = Maxi[rt] = f; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(ls, l, mid, pos, f);
  if (pos>mid) upd(rs, mid+1, r, pos, f);
  pushup(rt); return ;
}

int querys(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += querys(ls, l, mid, L, R);
  if (R>mid) ans += querys(rs, mid+1, r, L, R);
  return ans;
}

int querym(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return Maxi[rt];
  int mid = (l+r) >> 1, Max = -1e9;
  if (L<=mid) Max = max(Max, querym(ls, l, mid, L, R));
  if (R>mid) Max = max(Max, querym(rs, mid+1, r, L, R));
  return Max;
}

void dfs1(int cur, int Fa) {
  dep[cur] = dep[Fa] + 1;
  fa[cur] = Fa, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == Fa) continue;
    dfs1(to, cur);
    siz[cur] += siz[to];
    if (siz[to] > heavyson)
      son[cur] = to, heavyson = siz[to];
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++dfn;
  v[dfn] = w[cur], tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == fa[cur] || to == son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

int qus(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    int cur = querys(1, 1, n, id[tp[l]], id[l]);
    ans += cur, l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += querys(1, 1, n, id[l], id[r]);
  return ans;
}

int qum(int l, int r) {
  int ans = -1e9;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    int cur = querym(1, 1, n, id[tp[l]], id[l]);
    ans = max(ans, cur), l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = max(ans, querym(1, 1, n, id[l], id[r]));
  return ans;
}

int main() {
//   freopen("P2590.in", "r", stdin);
//   freopen("P2590.out", "w", stdout);
  read(n);
  for (int i=1; i<n; ++i) {
    int x, y; read(x), read(y);
    addEdge(x, y), addEdge(y, x);
  }
  for (int i=1; i<=n; ++i) read(w[i]);

  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);

  read(Q);
  while (Q--) {
    std::cin >> str+1;
    int l, r; read(l), read(r);
    if (str[1] == 'C') upd(1, 1, n, id[l], r);
    else if (str[2] == 'M') out(qum(l, r)), puts("");
    else if (str[2] == 'S') out(qus(l, r)), puts("");
  }
  return 0;
}

简单 trick。

只需要将依赖关系转化为树上关系就可以了。
然后就是要区分 0 和 unedited，完全不一样。
所以可以直接将 unedited 设置为 -1 然后乱搞即可。

注意是赋值而不是加法。

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
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 1e5 + 10;
int n, Q, cnt, idx, head[N];
int val[N<<2], lazy[N<<2];
int id[N], tp[N], siz[N], dep[N];
char opt[20]; int fa[N], son[N];

struct Edge { int to, nxt; } e[N];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  return ;
}

void pushdown(int rt, int l, int r) {
  if (lazy[rt]<0) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rt], lazy[rs] = lazy[rt];
  val[ls] = lazy[rt] * (mid-l+1);
  val[rs] = lazy[rt] * (r-mid);
  lazy[rt] = -1; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) {
    lazy[rt] = f; val[rt] = f * (r-l+1);
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx; tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

void up(int l, int r, int f) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], f);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], f);
  return ;
}

int main() {
//   freopen("P2146.in", "r", stdin);
  memset(lazy, -1, sizeof lazy);
  read(n);
  for (int i=2; i<=n; ++i) {
    int v; read(v);
    addEdge(v+1, i);
  }
  dfs1(1, 1), dfs2(1, 1), read(Q);
  while (Q--) {
    cin >> opt+1;
    int v; read(v); ++v;
    int cur = query(1, 1, n, 1, n);
    if (opt[1]=='i') up(1, v, 1);
    else if (opt[1]=='u') upd(1, 1, n, id[v], id[v]+siz[v]-1, 0);
    int to = query(1, 1, n, 1, n);
    printf("%d\n", abs(cur-to));
  }
  return 0;
}

也是个简单题，就是不要被 from 和 to 骗了，双向边肯定要连的。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  }
  ret *= f; return ;
}

const int N = 1e5 + 10;

int n, m, cnt, idx;
int dep[N], son[N], fa[N], siz[N];
int head[N<<1], tp[N], w[N], wl[N], id[N];
struct Edge { int to, nxt; } e[N<<1];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

int lazy[N<<2], val[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  return ;
}

void build(int rt, int l, int r) {
  if (l==r) { val[rt] = wl[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
  val[ls] += (mid-l+1) * lazy[rt];
  val[rs] += (r-mid) * lazy[rt];
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) { lazy[rt] += f; val[rt] += f * (r-l+1); return ; }
  int mid = (l+r) >> 1; pushdown(rt, l, r);
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  int ans = 0, mid = (l+r) >> 1;
  pushdown(rt, l, r);
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void dfs1(int cur, int f) {
  fa[cur] = f, siz[cur] = 1;
  dep[cur] = dep[f] + 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==f) continue;
    dfs1(to, cur); siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx, wl[idx] = w[cur];
  tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa[cur] || to==son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

int que(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans += query(1, 1, n, id[tp[l]], id[l]);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += query(1, 1, n, id[l], id[r]);
  return ans;
}

signed main() {
  read(n), read(m);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);
  while (m--) {
    int opt, x, a; read(opt), read(x);
    if (opt==1) {
      read(a);
      upd(1, 1, n, id[x], id[x], a);
    } else if (opt==2) {
      read(a);
      upd(1, 1, n, id[x], id[x]+siz[x]-1, a);
    } else printf("%lld\n", que(1, x));
  }
  return 0;
}

毒瘤出题人搞边不搞点。

看到题目首先想到树链剖分。
首先变为重边的操作不难，直接普通树链剖分即可。
查询路径上包含所有重边也很简单，只需要标记为 1 然后统计和。

但是 ex 的在于将点 $x$ 的所有连边变为轻边。

所以应该怎么弄呢？
那么很容易想到树链剖分的染色。

可以这样做：每一次路径变为重边就可以看成是给路径上所有点染一种 新的 颜色。
那么这个时候，看到所有其他连边连向的点都和当前路径上点的颜色不一样。
这个时候就可以默认其变为了轻边。

所以这样就可以得出判断轻边的条件了。
就是一条边，如果它两端颜色相同就为重边。
证明显然。

然后就是关于区间修改的问题了。
因为当前是求区间两端颜色相同边的个数，所以考虑树链剖分，将一段路径拆成若干区间，每一次合并区间都可以加上子区间答案，并保证其正确性，显而易见这样是不会假掉的。
要注意的就是如果子区间中间连接的两点颜色相同答案要加上 $1$。

那路径修改呢？这样还是有很大区别的。
因为两点之间路径可以视作从一个点剖开变成两条路径。
所以考虑两条路径分别维护。

那么我们可以对于每一个跳链顶的过程，记录当前 update 的是以 $u$ 为起点的路径还是以 $v$ 为起点的路径（$u \rightarrow v$ 为路径），每一次看维护两个指针 L 和 R 是否交换即可，最后还要合并答案，这里还是要详细讲一下。

不考虑整条路径两个指针 L，R 的实际位置，只考虑相对位置。
那么有两种情况。

  • L 跳到了但是 R 没有跳到。

显然这个时候 dep[L]<dep[R]。
又因为 L 跳到了，所以上一次更新的是 L 路径，本次就要更新 R 路径了。
所以本轮不用交换 L 和 R，L 路径和 R 路径的 tag 仍然指向 L。
这里就是容易弄混的地方，指向 L 的 tag 在这时要更新 R 路径。

  • R 跳到了但是 L 没有跳到。

显然这个时候 dep[L]>dep[R]。
又因为 R 跳到了，所以上面的 tag 指向 R，本次更新 L 路径。
因为当前这样所以要交换 L 和 R，tag 反转之后指向当前 R，所以相当于更新交换之后的 R 路径，本质还是 L 路径。（我自己都晕了）
反正不偷懒的写法会好理解一些，手动模拟比较好一点。

大概就是分 L 先到和 R 先到的情况吧。
其实手玩一下也是没有问题的，手玩完之后再写暴力更新的代码。

另外一点，我这里默认 L 路径在左边，其 dep[l]>dep[r]。
而 R 路径默认在右边，其 dep[l]<dep[r]。

lc 和 rc 分别是 leftcolor，rightcolor。

注意一开始如果全部没有染色那默认全都为 $0$，那么重边的条数就变成 $n-1$ 了，which is totally wrong。所以一开始就要染奇奇怪怪的颜色。
接着注意边数等于点数减一，在 pushdown 和 update 的时候要注意。

代码如下。

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
165
166
167
168
169
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int T, n, m, cnt, idx, lazy[N<<2];
int head[N<<1], dep[N], siz[N];
int tp[N], son[N], fa[N], id[N];

struct Edge { int to, nxt; } e[N<<1];
struct seg {
  int lc, rc, val;
  seg(int lc, int rc, int val):
    lc(lc), rc(rc), val(val) {}
  seg() {}
} tree[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  tree[rt].lc = tree[ls].lc;
  tree[rt].rc = tree[rs].rc;
  tree[rt].val = tree[ls].val + tree[rs].val;
  if (tree[ls].rc == tree[rs].lc) ++tree[rt].val;
  return ;
}

seg Merge(seg L, seg R) {
  seg cur; cur.lc = L.lc, cur.rc = R.rc;
  cur.val = L.val + R.val;
  if (L.rc == R.lc) ++cur.val;
  return cur;
}

void pushdown(int rt, int l, int r) {
  // lazy[rt] -> stores the color
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rs] = lazy[rt];
  tree[ls] = seg(lazy[rt], lazy[rt], mid-l); // (mid-l+1)-1
  tree[rs] = seg(lazy[rt], lazy[rt], r-mid-1); // (r-mid)-1
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int col) {
  if (L<=l && r<=R) {
    lazy[rt] = col;
    tree[rt] = seg(col, col, r-l); // (r-l+1)-1
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, col);
  if (R>mid) upd(rs, mid+1, r, L, R, col);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, tag = 0;
  seg ans1, ans2;
  if (L<=mid) ans1 = query(ls, l, mid, L, R), ++tag;
  if (R>mid) ans2 = query(rs, mid+1, r, L, R), tag += 2;
  if (tag == 1) return ans1; else if (tag == 2) return ans2;
  return Merge(ans1, ans2);
}

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == son[cur] || to == fa[cur]) continue;
    dfs2(to, to);
  } return ;
}

void up(int l, int r, int col) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], col);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], col);
  return ;
}

const seg NUL = seg(0, 0, 0);
int qu(int l, int r) {
  int belong = 0; seg ans[2];
  ans[0] = seg(0, 0, 0), ans[1] = ans[0];
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) {
      belong = 1 - belong;
      swap(l, r);
    }
    seg cur = query(1, 1, n, id[tp[l]], id[l]);
    if (belong) ans[1] = Merge(cur, ans[1]);
    else ans[0] = seg(ans[0].lc, cur.lc,
    ans[0].val+cur.val+(ans[0].rc==cur.rc));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) {
    belong = 1 - belong;
    swap(l, r);
  }
  seg cur = query(1, 1, n, id[l], id[r]);
  if (!belong) ans[1] = Merge(cur, ans[1]);
  else ans[0] = seg(ans[0].lc, cur.lc,
  ans[0].val+cur.val+(ans[0].rc==cur.rc));
  return Merge(ans[0], ans[1]).val;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(T);
  while (T--) {
    read(n), read(m);
    cnt = idx = 0;
    for (int i=1; i<=n; ++i) {
      siz[i] = dep[i] = son[i] = 0;
      id[i] = tp[i] = fa[i] = head[i] = 0;
      tree[i*4-3] = tree[i*4-2] = tree[i*4-1] = tree[i*4] = NUL;
      lazy[i*4-3] = lazy[i*4-2] = lazy[i*4-1] = lazy[i*4] = 0;
    }
    for (int i=1; i<n; ++i) {
      int u, v; read(u), read(v);
      addEdge(u, v), addEdge(v, u);
    }
    dfs1(1, 1), dfs2(1, 1);
    for (int i=1; i<=n; ++i) upd(1, 1, n, id[i], id[i], -i);
    while (m--) {
      int opt, u, v; read(opt), read(u), read(v);
      if (opt == 1) up(u, v, m);
      else printf("%d\n", qu(u, v));
    }
  }
  return 0;
}

什么时候 NOI 能出一些不重复的题目啊 …（指 NOI2021 D1T1）
这个 trick 和上面一题几乎一致，但是这个时候初始贡献为 $1$。
每一次 update 的区间贡献都为 $1$，判断 ls.rc=rs.lc 那么贡献 $-1$。

代码如下。

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
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, cnt, idx, lazy[N<<2];
int head[N<<1], dep[N], siz[N];
int tp[N], son[N], fa[N], id[N];
int w[N], wl[N];

struct Edge { int to, nxt; } e[N<<1];
struct seg {
  int lc, rc, val;
  seg(int lc, int rc, int val):
    lc(lc), rc(rc), val(val) {}
  seg() {}
} tree[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  tree[rt].lc = tree[ls].lc;
  tree[rt].rc = tree[rs].rc;
  tree[rt].val = tree[ls].val + tree[rs].val;
  if (tree[ls].rc == tree[rs].lc) --tree[rt].val;
  return ;
}

seg Merge(seg L, seg R) {
  seg cur; cur.lc = L.lc, cur.rc = R.rc;
  cur.val = L.val + R.val;
  if (L.rc == R.lc) --cur.val;
  return cur;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rs] = lazy[rt];
  tree[ls] = seg(lazy[rt], lazy[rt], 1);
  tree[rs] = seg(lazy[rt], lazy[rt], 1);
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int col) {
  if (L<=l && r<=R) {
    lazy[rt] = col;
    tree[rt] = seg(col, col, 1);
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, col);
  if (R>mid) upd(rs, mid+1, r, L, R, col);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, tag = 0;
  seg ans1, ans2;
  if (L<=mid) ans1 = query(ls, l, mid, L, R), ++tag;
  if (R>mid) ans2 = query(rs, mid+1, r, L, R), tag += 2;
  if (tag == 1) return ans1; if (tag == 2) return ans2;
  return Merge(ans1, ans2);
}

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx, wl[idx] = w[cur];
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == fa[cur] || to == son[cur]) continue;
    dfs2(to, to);
  } return ;
}

void up(int l, int r, int col) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], col);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], col);
  return ;
}

const seg NUL = seg(0, 0, 0);
int qu(int l, int r) {
  int belong = 0; seg ans[2];
  ans[0] = ans[1] = NUL;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) {
      belong = 1 - belong;
      swap(l, r);
    }
    seg cur = query(1, 1, n, id[tp[l]], id[l]);
    if (belong) ans[1] = Merge(cur, ans[1]);
    else ans[0] = seg(ans[0].lc, cur.lc,
    ans[0].val+cur.val-(ans[0].rc==cur.rc));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) {
    belong = 1 - belong;
    swap(l, r);
  }
  seg cur = query(1, 1, n, id[l], id[r]);
  if (!belong) ans[1] = Merge(cur, ans[1]);
  else ans[0] = seg(ans[0].lc, cur.lc,
  ans[0].val+cur.val-(ans[0].rc==cur.rc));
  return Merge(ans[0], ans[1]).val;
}

void build(int rt, int l, int r) {
  if (l==r) {
    tree[rt].val = 1;
    tree[rt].lc = tree[rt].rc = wl[l];
    return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(n), read(m);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v), addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);
  while (m--) {
    char opt; cin >> opt;
    int u, v, color;
    read(u), read(v);
    if (opt == 'C') read(color), up(u, v, color);
    else printf("%d\n", qu(u, v));
  }
  return 0;
}

树链剖分专题

https://lbn233.github.io/2021/08/03/DS-On-Tree/

Author

Xcel

Posted on

2021-08-03

Updated on

2021-09-04

Licensed under

#
Follow

Links

Categories

Recents

Archives

Tags

DS5
Graph1
Math1
Network Flows1
Number Theory2
Others2
State Compression1

Subscribe for updates

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×