CF1192B Dynamic Diameter

算法

欧拉序
线段树

思路

对于这道题考虑使用欧拉序的性质：

对于树上的每一个子树，在欧拉序上都有一个区间与之对应。
对于 $(u, v)$ 的最近公共祖先，在欧拉序上表现为区间 $[pos_u, pos_v]$ 内深度最浅的节点。

所以可以将原树转化为欧拉序，将树上问题转化为序列上的区间问题，就可以使用线段树解决。

由于题目要求树的直径，所以用线段树查找区间最值，找到点 $(u, v)$ 的最近公共祖先 $lca$ ，则 $dist(u, v)$ 可以表示为：

\large dist(u,v) = dep_u + dep_v - 2 \cdot dep_{lca}

而直径就是 $\max\{dist(u, v)\}$ 。

所以原题目的问题就转化为：在欧拉序上找一个三元组 $(u, lca, v)$ ，满足如下条件：

$dep_u + dep_v - 2 \cdot dep_{lca}$ 最大。
$lca$ 为区间 $[pos_u, pos_v]$ 内深度最小的节点。

而第二个条件可以由第一个条件限制，所以可以忽略。

由上面两个限制条件我们可以得到线段树需要维护的数据：

$max$ ：区间最大值。
$min$ ：区间最小值。
$left\ mid$ （以下简称 $LM$ ）：三元组 $(u, lca, v)$ 中 $dep_u - 2 \cdot dep_{lca}$ 的最大值。
$mid\ right$ （以下简称 $RM$ ）：三元组 $(u, lca, v)$ 中 $dep_v - 2 \cdot dep_{lca}$ 的最大值。
$left\ mid\ right$ （以下简称 $LMR$ ）：三元组 $(u, lca, v)$ 中 $dep_u + dep_v - 2 \cdot dep_{lca}$ 的最大值。

接下来考虑如何转移（即为 push_up(int k) 函数）。对于 $max$ 和 $min$ 来说转移很简单，即为：

\large \begin{aligned} max_k &= \max(max_{lc}, max_{rc}) \\ min_k &= \min(min_{lc}, min_{rc}) \\ \end{aligned}

而对于 $LM$ 而言，可以从三个方向转移：

\large LM = \max(LM_{lc}, LM_{rc}, max_{lc} - 2 \cdot min_{rc})

对于 $MR$ 同理由：

\large MR = \max(MR_{lc}, MR_{rc}, -2 \cdot min_{lc} + max_{rc})

最后合并成 $LMR$ :

\large LMR = \max(LMR_{lc}, LMR_{rc}, LM_{lc} + max_{rc}, max_{lc} + MR_{rc})

代码

1
#include <bits/stdc++.h>
2
#define OnlineJudge
3

4
constexpr int N = 1e5 + 5;
5
std::vector<int> euler_seq{-1};
6
int in[N], out[N], num = 0;
7
int head[N], cnt = 0;
8
int n, q, u, v, fa[N];
9
long long W, d, w, last = 0ll, dist[N];
10
std::vector<std::tuple<int, int, long long>> input_edges;
11

12
class Edge {
13
 public:
14
  int to, next;
15
  long long w;
16

17
} edges[N << 4];
18

19
void add_edge(int u, int v, long long w) {
20
  edges[cnt].to = v;
21
  edges[cnt].w = w;
22
  edges[cnt].next = head[u];
23
  head[u] = cnt++;
24
}
25

26
class SegmentTree {
27
 private:
28
  class Values {
29
    public:
30
    // ! 对 lazy 要初始化（虽然在 build 里面写了，但不知道为什么有些还是没有初始化）
31
    long long max = 0, min = 0, left_mid = 0, mid_right = 0, left_mid_right = 0, lazy = 0;
32
  };
33

34
  class NodeInfo {
35
   public:
36
    int left = 0, right = 0;
37
    Values val;
38
  };
39

40
  public:
41
  NodeInfo tr[N << 2];
42

43
  Values merge_tags(Values a, Values b) {
44
    Values retval;
45

46
    retval.max = std::max(a.max, b.max);
47
    retval.min = std::min(a.min, b.min);
48
    retval.left_mid = std::max({a.left_mid, b.left_mid, a.max + -2 * b.min});
49
    retval.mid_right = std::max({a.mid_right, b.mid_right, -2 * a.min + b.max});
50
    retval.left_mid_right = std::max({a.left_mid_right, b.left_mid_right, a.left_mid + b.max, a.max + b.mid_right});
51

52
    return retval;
53
  }
54

55
  void modify_tags(Values& root, long long value) {
56
    root.lazy += value;
57
    root.max += value;
58
    root.min += value;
59
    root.left_mid -= value;
60
    root.mid_right -= value;
61
  }
62

63
  void push_up(int k) {
64
    Values lc = tr[k << 1].val, rc = tr[k << 1 | 1].val;
65

66
    int temp = tr[k].val.lazy;
67
    tr[k].val = merge_tags(lc, rc);
68
    tr[k].val.lazy = temp;
69
  }
70

71
  void push_down(int k) {
72
    if (tr[k].val.lazy == 0) {
73
      return void();
74
    }
75

76
    modify_tags(tr[k << 1].val, tr[k].val.lazy);
77
    modify_tags(tr[k << 1 | 1].val, tr[k].val.lazy);
78

79
    tr[k].val.lazy = 0;
80
  }
81

82
  void build_tree(int k, int l, int r) {
83
    tr[k].left = l;
84
    tr[k].right = r;
85
    tr[k].val.lazy = 0;
86

87
    if (tr[k].left == tr[k].right) {
88
      tr[k].val.max = tr[k].val.min = dist[euler_seq[l]];
89
      tr[k].val.left_mid = tr[k].val.mid_right = -dist[euler_seq[l]];
90
      tr[k].val.left_mid_right = 0;
91

92
      #ifndef OnlineJudge
93
      std::cout << "BUILD:\n";
94
      std::cout << k << " " << tr[k].left << " " << tr[k].right << " ";
95
      std::cout << tr[k].val.max << " " << tr[k].val.min << " " << tr[k].val.left_mid << " ";
96
      std::cout << tr[k].val.mid_right << ' ' << tr[k].val.left_mid_right << " " << tr[k].val.lazy << '\n';
97
      #endif
98

99
      return void();
100
    }
101

102
    int mid = (tr[k].left + tr[k].right) >> 1;
103
    int lc = k << 1, rc = k << 1 | 1;
104

105
    build_tree(lc, l, mid);
106
    build_tree(rc, mid + 1, r);
107

108
    push_up(k);
109

110
    #ifndef OnlineJudge
111
    std::cout << "BUILD:\n";
112
    std::cout << k << " " << tr[k].left << " " << tr[k].right << " ";
113
    std::cout << tr[k].val.max << " " << tr[k].val.min << " " << tr[k].val.left_mid << " ";
114
    std::cout << tr[k].val.mid_right << ' ' << tr[k].val.left_mid_right << " " << tr[k].val.lazy << '\n';
115
    #endif
116
  }
117

118
  void modify(int k, int l, int r, long long value) {
119
    #ifndef OnlineJudge
120
    std::cout << "MODIFY:\n";
121
    std::cout << k << " " << tr[k].left << " " << tr[k].right << " ";
122
    std::cout << tr[k].val.max << " " << tr[k].val.min << " " << tr[k].val.left_mid << " ";
123
    std::cout << tr[k].val.mid_right << ' ' << tr[k].val.left_mid_right << " " << tr[k].val.lazy << '\n';
124
    #endif
125

126
    if (tr[k].left >= l && tr[k].right <= r) {
127
      modify_tags(tr[k].val, value);
128
      return void();
129
    }
130

131
    push_down(k);
132

133
    int mid = (tr[k].left + tr[k].right) >> 1;
134
    int lc = k << 1, rc = k << 1 | 1;
135

136
    if (r <= mid) {
137
      modify(lc, l, r, value);
138
    } else if (l > mid) {
139
      modify(rc, l, r, value);
140
    } else {
141
      modify(lc, l, mid, value);
142
      modify(rc, mid + 1, r, value);
143
    }
144

145
    push_up(k);
146
  }
147

148
  Values query(int k, int l, int r) {
149
    #ifndef OnlineJudge
150
    std::cout << "QUERY:\n";
151
    std::cout << k << " " << tr[k].left << " " << tr[k].right << " ";
152
    std::cout << tr[k].val.max << " " << tr[k].val.min << " " << tr[k].val.left_mid << " ";
153
    std::cout << tr[k].val.mid_right << ' ' << tr[k].val.left_mid_right << " " << tr[k].val.lazy << '\n';
154
    #endif
155

156
    if (tr[k].left >= l && tr[k].right <= r) {
157
      return tr[k].val;
158
    }
159

160
    push_down(k);
161

162
    int mid = (tr[k].left + tr[k].right) >> 1;
163
    int lc = k << 1, rc = k << 1 | 1;
164

165
    if (r <= mid) {
166
      return query(lc, l, r);
167
    } else if (l > mid) {
168
      return query(rc, l, r);
169
    } else {
170
      return merge_tags(query(lc, l, mid), query(rc, mid + 1, r));
171
    }
172
  }
173
} data;
174

175
void dfs(int u, int father) {
176
  euler_seq.emplace_back(u);
177
  in[u] = euler_seq.size() - 1;
178

179
  for (int i = head[u]; ~i; i = edges[i].next) {
180
    int v = edges[i].to;
181
    if (v == father) continue;
182

183
    fa[v] = u;
184
    dist[v] = dist[u] + edges[i].w;
185
    dfs(v, u);
186
    euler_seq.emplace_back(u);
187
  }
188

189
  out[u] = euler_seq.size() - 1;
190
}
191

192
int main() {
193
  std::ios::sync_with_stdio(false);
194
  std::cin.tie(nullptr);
195
  std::cout.tie(nullptr);
196

197
  std::memset(head, -1, sizeof(head));
198

199
  std::cin >> n >> q >> W;
200

201
  for (int i = 1; i < n; i ++) {
202
    std::cin >> u >> v >> w;
203

204
    add_edge(u, v, w);
205
    add_edge(v, u, w);
206
    input_edges.emplace_back(u, v, w);
207
  }
208

209
  dfs(1, 1);
210

211
  // ! 注意调换顺序，保证前面一个点是后面一个点的父亲
212
  for (int i = 0; i < n - 1; i ++) {
213
    if (fa[std::get<0>(input_edges[i])] == std::get<1>(input_edges[i])) {
214
      std::swap(std::get<0>(input_edges[i]), std::get<1>(input_edges[i]));
215
    }
216
  }
217

218
  data.build_tree(1, 1, euler_seq.size() - 1);
219

220
  #ifndef OnlineJudge
221
  std::cout << data.query(1, 1, euler_seq.size() - 1).left_mid_right << '\n';
222
  for (auto&& [u, v, w] : input_edges) {
223
    std::cout << u << ' ' << v << ' ' << w << '\n';
224
  }
225
  #endif
226

227
  last = 0;
228
  for (int i = 1; i <= q; i ++) {
229
    std::cin >> d >> w;
230
    d = (d + last) % (n - 1);
231
    w = (w + last) % W;
232

233
    // ! 对于边 (u, v, w)，满足 fa[v] == u，则修改后的 w' 只对 v 的子树有影响，所以只更新 v 的子树即可。
234
    data.modify(1, in[std::get<1>(input_edges[d])], out[std::get<1>(input_edges[d])], w - std::get<2>(input_edges[d]));
235
    // ! 记得将边的信息更新
236
    std::get<2>(input_edges[d]) = w;
237
    last = data.query(1, 1, euler_seq.size() - 1).left_mid_right;
238

239
    std::cout << last << '\n';
240
  }
241

242
  return 0;
243
}