#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
using i64 = long long;
struct node {
i64 w, h_mx, l_mx, l_smx, p_mx, dp, e;
node() : node(0, 0, 0, 0, 0, 0, 1) {}
explicit node(i64 w, i64 mx, i64 smx, i64 dp) :
node(w, w, mx, smx, w + mx, max(w + mx, dp), 0) {}
explicit node(i64 w, i64 h_mx, i64 l_mx, i64 l_smx, i64 p_mx, i64 dp, i64 e) :
w(w), h_mx(h_mx), l_mx(l_mx), l_smx(l_smx), p_mx(p_mx), dp(dp), e(e) {}
};
ostream& operator<< (ostream& out, const node& x) {
out << '(' << x.w << ' ' << x.h_mx << ' ' << x.l_mx << ' ' << x.l_smx << ' ' << x.p_mx << ' ' << x.dp << ' ' << x.e << ')';
return out;
}
node merge(const node& a, const node& b) {
if (a.e) return b;
if (b.e) return a;
node res{};
res.w = b.w + a.w;
res.h_mx = max(max(b.h_mx, b.l_mx) + a.w, a.h_mx);
res.l_mx = a.l_mx;
res.l_smx = a.l_smx;
res.p_mx = max(b.p_mx, b.w + a.p_mx);
res.dp = max({
b.dp,
a.dp,
max(b.h_mx, b.l_mx) + a.p_mx,
res.h_mx + res.l_mx,
res.l_mx + res.l_smx });
res.e = 0;
return res;
}
struct segtree {
segtree() : segtree(0) {}
explicit segtree(int n) : sz(1 << __lg(n - 1) + 1), tree(sz << 1) {}
void update(int i, const node& x) {
tree[--i |= sz] = x;
while (i >>= 1) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
}
node query(int l, int r) const {
node acc_l, acc_r;
for (--l |= sz, --r |= sz; l <= r; l >>= 1, r >>= 1) {
if (l & 1) acc_l = merge(acc_l, tree[l++]);
if (~r & 1) acc_r = merge(tree[r--], acc_r);
}
return merge(acc_l, acc_r);
}
private:
const int sz;
vector<node> tree;
};
int main() {
fastio;
int n, q; cin >> n >> q;
i64 w; cin >> w;
vector e(n - 1, tuple(0, 0, 0LL));
vector adj(n + 1, vector(0, 0));
for (auto& [a, b, c] : e) {
cin >> a >> b >> c;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector sz(n + 1, 1), dep(n + 1, 0), par(n + 1, 0);
vector in(n + 1, 0), inv_in(n + 1, 0), top(n + 1, 0), bot(n + 1, 0);
{
auto dfs1 = [&](const auto& f, int cur, int prv) -> void {
auto it = find(adj[cur].begin(), adj[cur].end(), prv);
if (it != adj[cur].end()) adj[cur].erase(it);
for (auto& nxt : adj[cur]) {
dep[nxt] = dep[cur] + 1;
par[nxt] = cur;
f(f, nxt, cur);
sz[cur] += sz[nxt];
if (sz[adj[cur][0]] < sz[nxt]) swap(adj[cur][0], nxt);
}
};
dfs1(dfs1, 1, 0);
int ord = 0;
auto dfs2 = [&](const auto& f, int cur) -> void {
in[cur] = ++ord;
inv_in[in[cur]] = cur;
for (int nxt : adj[cur]) {
top[nxt] = nxt == adj[cur][0] ? top[cur] : nxt;
f(f, nxt);
}
bot[cur] = adj[cur].size() ? bot[adj[cur][0]] : cur;
};
dfs2(dfs2, top[1] = 1);
}
vector cost(n + 1, 0LL);
for (auto& [a, b, c] : e) {
if (par[a] == b) swap(a, b);
cost[b] = c;
}
segtree tree(n);
vector acc_dp(n + 1, multiset{ 0LL });
vector acc_chain(n + 1, multiset{ 0LL, 0LL });
auto get_mx = [](const auto& ms) { return *prev(ms.end()); };
auto get_smx = [](const auto& ms) { return *prev(prev(ms.end())); };
auto get_node = [&](int i) {
if (adj[i].empty()) return node();
int c = adj[i][0];
return node(cost[c], get_mx(acc_chain[i]), get_smx(acc_chain[i]), get_mx(acc_dp[i]));
};
for (int _ = n; _ >= 1; _--) {
int i = inv_in[_];
tree.update(in[i], get_node(i));
if (i == top[i]) {
node res = tree.query(in[i], in[bot[i]]);
acc_dp[par[i]].insert(res.dp);
acc_chain[par[i]].insert(cost[i] + max(res.h_mx, res.l_mx));
}
}
auto update = [&](int i, i64 c) {
int cnt = 0;
while (i) {
{
node res = tree.query(in[top[i]], in[bot[i]]);
acc_dp[par[top[i]]].erase(acc_dp[par[top[i]]].find(res.dp));
acc_chain[par[top[i]]].erase(acc_chain[par[top[i]]].find(cost[top[i]] + max(res.h_mx, res.l_mx)));
}
if (++cnt == 1) {
cost[i] = c;
if (i != top[i]) {
int p = par[i];
tree.update(in[p], get_node(p));
}
}
tree.update(in[i], get_node(i));
{
node res = tree.query(in[top[i]], in[bot[i]]);
acc_dp[par[top[i]]].insert(res.dp);
acc_chain[par[top[i]]].insert(cost[top[i]] + max(res.h_mx, res.l_mx));
}
i = par[top[i]];
}
return get_mx(acc_dp[0]);
};
i64 res = 0;
while (q--) {
i64 i, c; cin >> i >> c;
i = (i + res) % (n - 1);
c = (c + res) % w;
auto [a, b, _] = e[i];
res = update(b, c);
cout << res << '\n';
}
}
Compilation message
diameter.cpp: In constructor 'segtree::segtree(int)':
diameter.cpp:42:48: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
42 | explicit segtree(int n) : sz(1 << __lg(n - 1) + 1), tree(sz << 1) {}
| ~~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
984 KB |
Output is correct |
2 |
Correct |
14 ms |
1104 KB |
Output is correct |
3 |
Correct |
86 ms |
1588 KB |
Output is correct |
4 |
Correct |
134 ms |
2320 KB |
Output is correct |
5 |
Correct |
11 ms |
6232 KB |
Output is correct |
6 |
Correct |
34 ms |
6492 KB |
Output is correct |
7 |
Correct |
131 ms |
6960 KB |
Output is correct |
8 |
Correct |
213 ms |
8148 KB |
Output is correct |
9 |
Correct |
44 ms |
27728 KB |
Output is correct |
10 |
Correct |
72 ms |
27728 KB |
Output is correct |
11 |
Correct |
178 ms |
28496 KB |
Output is correct |
12 |
Correct |
318 ms |
29340 KB |
Output is correct |
13 |
Correct |
90 ms |
54940 KB |
Output is correct |
14 |
Correct |
120 ms |
55124 KB |
Output is correct |
15 |
Correct |
248 ms |
55924 KB |
Output is correct |
16 |
Correct |
406 ms |
56716 KB |
Output is correct |
17 |
Correct |
756 ms |
56404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
663 ms |
58368 KB |
Output is correct |
2 |
Correct |
678 ms |
58428 KB |
Output is correct |
3 |
Correct |
702 ms |
58452 KB |
Output is correct |
4 |
Correct |
625 ms |
58388 KB |
Output is correct |
5 |
Correct |
672 ms |
58968 KB |
Output is correct |
6 |
Correct |
651 ms |
61344 KB |
Output is correct |
7 |
Correct |
410 ms |
60496 KB |
Output is correct |
8 |
Correct |
448 ms |
60384 KB |
Output is correct |
9 |
Correct |
427 ms |
60400 KB |
Output is correct |
10 |
Correct |
415 ms |
60544 KB |
Output is correct |
11 |
Correct |
409 ms |
60884 KB |
Output is correct |
12 |
Correct |
367 ms |
62924 KB |
Output is correct |
13 |
Correct |
363 ms |
62268 KB |
Output is correct |
14 |
Correct |
343 ms |
62236 KB |
Output is correct |
15 |
Correct |
336 ms |
62288 KB |
Output is correct |
16 |
Correct |
319 ms |
62228 KB |
Output is correct |
17 |
Correct |
337 ms |
62520 KB |
Output is correct |
18 |
Correct |
297 ms |
63388 KB |
Output is correct |
19 |
Correct |
352 ms |
62172 KB |
Output is correct |
20 |
Correct |
325 ms |
62156 KB |
Output is correct |
21 |
Correct |
335 ms |
62464 KB |
Output is correct |
22 |
Correct |
312 ms |
62292 KB |
Output is correct |
23 |
Correct |
366 ms |
62372 KB |
Output is correct |
24 |
Correct |
296 ms |
63320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |