#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using i64 = long long;
struct Edge {
int to;
i64 w;
};
using T = std::pair<i64, int>;
T op(const T& a, const T& b) {
return std::max(a, b);
}
T e() {
return {0, 0};
}
using U = i64;
T map(i64 a, const T& b) {
return {b.first + a, b.second};
}
i64 composite(i64 a, i64 b) {
return a + b;
}
i64 id() {
return 0;
}
class lazySegtree {
int n, logn, size;
std::vector<T> node;
std::vector<U> lazy;
void update(int i) {
node[i] = op(node[2 * i], node[2 * i + 1]);
}
void all_apply(int i, U f) {
node[i] = map(f, node[i]);
if (i < size) lazy[i] = composite(f, lazy[i]);
}
void push(int i) {
all_apply(2 * i, lazy[i]);
all_apply(2 * i + 1, lazy[i]);
lazy[i] = id();
}
public:
lazySegtree() {}
lazySegtree(std::vector<T> initVec) {
n = (int)initVec.size();
logn = 0;
while ((1 << logn) < n) {
++logn;
}
size = 1 << logn;
node.assign(2 * size, e());
lazy.assign(size, id());
std::copy(initVec.begin(), initVec.end(), node.begin() + size);
for (int i = size - 1; i >= 1; --i) {
update(i);
}
}
void apply(int l, int r, U f) {
l += size, r += size;
for (int d = logn; d >= 1; --d) {
if (((l >> d) << d) != l) push(l >> d);
if (((r >> d) << d) != r) push((r - 1) >> d);
}
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l /= 2;
r /= 2;
}
l = l2, r = r2;
for (int d = 1; d <= logn; ++d) {
if (((l >> d) << d) != l) update(l >> d);
if (((r >> d) << d) != r) update((r - 1) >> d);
}
}
T fold(int l, int r) {
l += size, r += size;
for (int d = logn; d >= 1; --d) {
if (((l >> d) << d) != l) push(l >> d);
if (((r >> d) << d) != r) push((r - 1) >> d);
}
T pl = e(), pr = e();
while (l < r) {
if (l & 1) pl = op(pl, node[l++]);
if (r & 1) pr = op(node[--r], pr);
l /= 2;
r /= 2;
}
return op(pl, pr);
}
};
std::vector<std::vector<Edge>> tree;
struct TreeManager {
int n;
std::vector<char> isOn, isCentroid;
std::vector<int> size, in, out, fe, cen;
std::vector<int> revIn;
std::vector<i64> depth;
TreeManager() {}
TreeManager(const std::vector<char> &ison, const std::vector<int> &roots) {
isOn = ison;
n = tree.size();
isCentroid.assign(n, false);
size.assign(n, -1);
in.assign(n, -1);
out.assign(n, -1);
depth.assign(n, 0);
fe.assign(n, 0);
cen.assign(n, 0);
int id = 0;
for (const int v : roots) {
dfs1(v, -1);
int x = findCentroid(v, -1, size[v]);
dfs2(x, -1, id, 0, -1, x);
}
revIn.resize(n);
for (int i = 0; i < n; ++i) {
if (in[i] >= 0) {
revIn[in[i]] = i;
}
}
}
void dfs1(int v, int p) {
size[v] = 1;
for (const auto &[t, w] : tree[v]) {
if (t == p or (not isOn[t])) {
continue;
}
dfs1(t, v);
size[v] += size[t];
}
}
int findCentroid(int v, int p, int as) {
bool isCent = true;
for (const auto &[t, w] : tree[v]) {
if (t == p or (not isOn[t])) {
continue;
}
int res = findCentroid(t, v, as);
if (res != -1) {
return res;
}
if (size[t] > as / 2) {
isCent = false;
}
}
if ((as - size[v]) > as / 2) {
isCent = false;
}
isCentroid[v] = isCent;
return isCent ? v : -1;
}
void dfs2(int v, int p, int &id, i64 d, int f, int ce) {
fe[v] = f;
in[v] = id++;
cen[v] = ce;
depth[v] = d;
size[v] = 1;
for (const auto &[t, w] : tree[v]) {
if (t == p or (not isOn[t])) {
continue;
}
dfs2(t, v, id, d + w, (f == -1 ? t : f), ce);
size[v] += size[t];
}
out[v] = id;
}
};
int main() {
int N, Q;
i64 W;
std::cin >> N >> Q >> W;
std::vector<int> A(N - 1), B(N - 1);
std::vector<i64> C(N - 1);
tree.resize(N);
for (int i = 0; i < N - 1; ++i) {
std::cin >> A[i] >> B[i] >> C[i];
--A[i], --B[i];
tree[A[i]].push_back({B[i], C[i]});
tree[B[i]].push_back({A[i], C[i]});
}
std::vector<char> isOn(N, true);
std::vector<int> roots = {0};
std::vector<TreeManager> managers;
while (true) {
TreeManager mng(isOn, roots);
roots.clear();
for (int i = 0; i < N; ++i) {
if (not mng.isCentroid[i]) {
continue;
}
isOn[i] = false;
for (const auto &[t, w] : tree[i]) {
if (not isOn[t]) {
continue;
}
roots.push_back(t);
}
}
managers.push_back(std::move(mng));
if (std::none_of(isOn.begin(), isOn.end(), [](bool b) {
return b;
})) {
break;
}
}
const int m = (int)managers.size();
std::vector<lazySegtree> segs(m);
std::multiset<i64> diameters;
std::vector<i64> memoDiameters(N);
for (int x = 0; x < m; ++x) {
auto &mng = managers[x];
std::vector<std::pair<i64, int>> weighVec(N);
for (int i = 0; i < N; ++i) {
if (mng.in[i] == -1) {
continue;
}
weighVec[mng.in[i]].first = mng.depth[i];
}
for (int i = 0; i < N; ++i) {
weighVec[i].second = i;
}
segs[x] = lazySegtree(weighVec);
for (int i = 0; i < N; ++i) {
if (not mng.isCentroid[i]) {
continue;
}
if (mng.size[i] == 1) {
continue;
}
const int bl = mng.in[i], br = mng.out[i];
const auto [v, p] = segs[x].fold(bl, br);
const int l = mng.in[mng.fe[mng.revIn[p]]], r = mng.out[mng.fe[mng.revIn[p]]];
const auto v2 = std::max(segs[x].fold(bl, l).first, segs[x].fold(r, br).first);
diameters.insert(v + v2);
memoDiameters[i] = v + v2;
}
}
i64 last = 0;
while (Q--) {
int d;
i64 e;
std::cin >> d >> e;
i64 i = (last + d) % (N - 1);
i64 w = (last + e) % W;
int a = A[i], b = B[i];
for (int x = 0; x < m; ++x) {
auto &mng = managers[x];
if ((not mng.isOn[a]) or (not mng.isOn[b])) {
break;
}
if (mng.depth[a] > mng.depth[b]) {
std::swap(a, b);
}
const int c = mng.cen[a];
if (mng.size[c] == 1) {
break;
}
diameters.erase(diameters.find(memoDiameters[c]));
segs[x].apply(mng.in[b], mng.out[b], (w - C[i]));
const int bl = mng.in[c], br = mng.out[c];
const auto [v3, p3] = segs[x].fold(bl, br);
const int l = mng.in[mng.fe[mng.revIn[p3]]], r = mng.out[mng.fe[mng.revIn[p3]]];
const auto v2 = std::max(segs[x].fold(bl, l).first, segs[x].fold(r, br).first);
diameters.insert(v3 + v2);
memoDiameters[c] = v3 + v2;
}
C[i] = w;
last = *diameters.rbegin();
std::cout << last << std::endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
29 ms |
1128 KB |
Output is correct |
20 |
Correct |
30 ms |
1136 KB |
Output is correct |
21 |
Correct |
36 ms |
1108 KB |
Output is correct |
22 |
Correct |
42 ms |
1220 KB |
Output is correct |
23 |
Correct |
48 ms |
6020 KB |
Output is correct |
24 |
Correct |
59 ms |
7028 KB |
Output is correct |
25 |
Correct |
69 ms |
7528 KB |
Output is correct |
26 |
Correct |
76 ms |
7708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
4 ms |
212 KB |
Output is correct |
4 |
Correct |
40 ms |
340 KB |
Output is correct |
5 |
Correct |
187 ms |
716 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
5 ms |
444 KB |
Output is correct |
10 |
Correct |
44 ms |
468 KB |
Output is correct |
11 |
Correct |
214 ms |
832 KB |
Output is correct |
12 |
Correct |
5 ms |
1948 KB |
Output is correct |
13 |
Correct |
5 ms |
1876 KB |
Output is correct |
14 |
Correct |
9 ms |
1972 KB |
Output is correct |
15 |
Correct |
52 ms |
1924 KB |
Output is correct |
16 |
Correct |
242 ms |
2376 KB |
Output is correct |
17 |
Correct |
87 ms |
30536 KB |
Output is correct |
18 |
Correct |
93 ms |
30560 KB |
Output is correct |
19 |
Correct |
92 ms |
30472 KB |
Output is correct |
20 |
Correct |
140 ms |
30616 KB |
Output is correct |
21 |
Correct |
354 ms |
31136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1108 KB |
Output is correct |
2 |
Correct |
56 ms |
1124 KB |
Output is correct |
3 |
Correct |
249 ms |
1520 KB |
Output is correct |
4 |
Correct |
497 ms |
1536 KB |
Output is correct |
5 |
Correct |
33 ms |
14744 KB |
Output is correct |
6 |
Correct |
109 ms |
14748 KB |
Output is correct |
7 |
Correct |
438 ms |
15004 KB |
Output is correct |
8 |
Correct |
845 ms |
15276 KB |
Output is correct |
9 |
Correct |
137 ms |
72136 KB |
Output is correct |
10 |
Correct |
262 ms |
72232 KB |
Output is correct |
11 |
Correct |
813 ms |
72520 KB |
Output is correct |
12 |
Correct |
1541 ms |
72744 KB |
Output is correct |
13 |
Correct |
280 ms |
152336 KB |
Output is correct |
14 |
Correct |
425 ms |
152340 KB |
Output is correct |
15 |
Correct |
1091 ms |
152760 KB |
Output is correct |
16 |
Correct |
1926 ms |
152880 KB |
Output is correct |
17 |
Correct |
4016 ms |
153016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2999 ms |
152824 KB |
Output is correct |
2 |
Correct |
3037 ms |
153292 KB |
Output is correct |
3 |
Correct |
3147 ms |
144928 KB |
Output is correct |
4 |
Correct |
3165 ms |
161792 KB |
Output is correct |
5 |
Correct |
3030 ms |
153032 KB |
Output is correct |
6 |
Correct |
2695 ms |
151544 KB |
Output is correct |
7 |
Correct |
4043 ms |
163740 KB |
Output is correct |
8 |
Correct |
3994 ms |
163528 KB |
Output is correct |
9 |
Correct |
4075 ms |
163688 KB |
Output is correct |
10 |
Correct |
4011 ms |
163588 KB |
Output is correct |
11 |
Correct |
3945 ms |
163236 KB |
Output is correct |
12 |
Correct |
3557 ms |
161404 KB |
Output is correct |
13 |
Correct |
4433 ms |
165564 KB |
Output is correct |
14 |
Correct |
4604 ms |
169868 KB |
Output is correct |
15 |
Correct |
4594 ms |
169724 KB |
Output is correct |
16 |
Correct |
4673 ms |
169736 KB |
Output is correct |
17 |
Correct |
4454 ms |
169348 KB |
Output is correct |
18 |
Correct |
3801 ms |
167056 KB |
Output is correct |
19 |
Correct |
4722 ms |
169680 KB |
Output is correct |
20 |
Correct |
4502 ms |
169628 KB |
Output is correct |
21 |
Correct |
4494 ms |
169856 KB |
Output is correct |
22 |
Correct |
4404 ms |
169668 KB |
Output is correct |
23 |
Correct |
4412 ms |
169316 KB |
Output is correct |
24 |
Correct |
3878 ms |
167252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
29 ms |
1128 KB |
Output is correct |
20 |
Correct |
30 ms |
1136 KB |
Output is correct |
21 |
Correct |
36 ms |
1108 KB |
Output is correct |
22 |
Correct |
42 ms |
1220 KB |
Output is correct |
23 |
Correct |
48 ms |
6020 KB |
Output is correct |
24 |
Correct |
59 ms |
7028 KB |
Output is correct |
25 |
Correct |
69 ms |
7528 KB |
Output is correct |
26 |
Correct |
76 ms |
7708 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
4 ms |
212 KB |
Output is correct |
30 |
Correct |
40 ms |
340 KB |
Output is correct |
31 |
Correct |
187 ms |
716 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
5 ms |
444 KB |
Output is correct |
36 |
Correct |
44 ms |
468 KB |
Output is correct |
37 |
Correct |
214 ms |
832 KB |
Output is correct |
38 |
Correct |
5 ms |
1948 KB |
Output is correct |
39 |
Correct |
5 ms |
1876 KB |
Output is correct |
40 |
Correct |
9 ms |
1972 KB |
Output is correct |
41 |
Correct |
52 ms |
1924 KB |
Output is correct |
42 |
Correct |
242 ms |
2376 KB |
Output is correct |
43 |
Correct |
87 ms |
30536 KB |
Output is correct |
44 |
Correct |
93 ms |
30560 KB |
Output is correct |
45 |
Correct |
92 ms |
30472 KB |
Output is correct |
46 |
Correct |
140 ms |
30616 KB |
Output is correct |
47 |
Correct |
354 ms |
31136 KB |
Output is correct |
48 |
Correct |
7 ms |
1108 KB |
Output is correct |
49 |
Correct |
56 ms |
1124 KB |
Output is correct |
50 |
Correct |
249 ms |
1520 KB |
Output is correct |
51 |
Correct |
497 ms |
1536 KB |
Output is correct |
52 |
Correct |
33 ms |
14744 KB |
Output is correct |
53 |
Correct |
109 ms |
14748 KB |
Output is correct |
54 |
Correct |
438 ms |
15004 KB |
Output is correct |
55 |
Correct |
845 ms |
15276 KB |
Output is correct |
56 |
Correct |
137 ms |
72136 KB |
Output is correct |
57 |
Correct |
262 ms |
72232 KB |
Output is correct |
58 |
Correct |
813 ms |
72520 KB |
Output is correct |
59 |
Correct |
1541 ms |
72744 KB |
Output is correct |
60 |
Correct |
280 ms |
152336 KB |
Output is correct |
61 |
Correct |
425 ms |
152340 KB |
Output is correct |
62 |
Correct |
1091 ms |
152760 KB |
Output is correct |
63 |
Correct |
1926 ms |
152880 KB |
Output is correct |
64 |
Correct |
4016 ms |
153016 KB |
Output is correct |
65 |
Correct |
2999 ms |
152824 KB |
Output is correct |
66 |
Correct |
3037 ms |
153292 KB |
Output is correct |
67 |
Correct |
3147 ms |
144928 KB |
Output is correct |
68 |
Correct |
3165 ms |
161792 KB |
Output is correct |
69 |
Correct |
3030 ms |
153032 KB |
Output is correct |
70 |
Correct |
2695 ms |
151544 KB |
Output is correct |
71 |
Correct |
4043 ms |
163740 KB |
Output is correct |
72 |
Correct |
3994 ms |
163528 KB |
Output is correct |
73 |
Correct |
4075 ms |
163688 KB |
Output is correct |
74 |
Correct |
4011 ms |
163588 KB |
Output is correct |
75 |
Correct |
3945 ms |
163236 KB |
Output is correct |
76 |
Correct |
3557 ms |
161404 KB |
Output is correct |
77 |
Correct |
4433 ms |
165564 KB |
Output is correct |
78 |
Correct |
4604 ms |
169868 KB |
Output is correct |
79 |
Correct |
4594 ms |
169724 KB |
Output is correct |
80 |
Correct |
4673 ms |
169736 KB |
Output is correct |
81 |
Correct |
4454 ms |
169348 KB |
Output is correct |
82 |
Correct |
3801 ms |
167056 KB |
Output is correct |
83 |
Correct |
4722 ms |
169680 KB |
Output is correct |
84 |
Correct |
4502 ms |
169628 KB |
Output is correct |
85 |
Correct |
4494 ms |
169856 KB |
Output is correct |
86 |
Correct |
4404 ms |
169668 KB |
Output is correct |
87 |
Correct |
4412 ms |
169316 KB |
Output is correct |
88 |
Correct |
3878 ms |
167252 KB |
Output is correct |
89 |
Correct |
3069 ms |
156428 KB |
Output is correct |
90 |
Correct |
3321 ms |
165192 KB |
Output is correct |
91 |
Correct |
3891 ms |
165720 KB |
Output is correct |
92 |
Correct |
4121 ms |
167076 KB |
Output is correct |
93 |
Correct |
4293 ms |
168044 KB |
Output is correct |
94 |
Correct |
4294 ms |
168472 KB |
Output is correct |
95 |
Correct |
4519 ms |
168388 KB |
Output is correct |
96 |
Correct |
4447 ms |
168188 KB |
Output is correct |
97 |
Correct |
4438 ms |
168264 KB |
Output is correct |
98 |
Correct |
4466 ms |
168992 KB |
Output is correct |
99 |
Correct |
4534 ms |
168324 KB |
Output is correct |
100 |
Correct |
4628 ms |
168268 KB |
Output is correct |