#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
struct SegmentSegmentTree {
int lv;
vector<pll> d;
vector<ll> ins;
//1..n
SegmentSegmentTree(int n) {
lv = 2;
while(lv < n + 2)
lv *= 2;
d.resize(2 * lv + 3, {-1e18, 0});
ins.resize(2 * lv + 3);
for(int i = 1 ; i <= lv ; i++)
d[lv + i - 1].Y = i;
}
void initv(int i, ll x) {
d[lv + i - 1].X = x;
}
void process_init() {
for(int i = lv - 1 ; i >= 1 ; i--)
d[i] = max(d[2 * i], d[2 * i + 1]);
}
void insert(int a, int b, int l, int r, int w, ll x) {
if(a > r || b < l || l > r)
return ;
if(a <= l && r <= b) {
ins[w] += x;
d[w].X += x;
return;
}
insert(a, b, l, (l + r) / 2, 2 * w, x);
insert(a, b, (l + r) / 2 + 1, r, 2 * w + 1, x);
d[w] = max(d[2 * w], d[2 * w + 1]);
d[w].X += ins[w];
}
void insert(int a, int b, ll x) {
insert(a, b, 1, lv, 1, x);
}
pll query(int a, int b, int l, int r, int w) {
if(a > r || b < l || l > r)
return {-1e18, 0};
if(a <= l && r <= b)
return d[w];
pll p1 = query(a, b, l, (l + r) / 2, 2 * w);
pll p2 = query(a, b, (l + r) / 2 + 1, r, 2 * w + 1);
p1 = max(p1, p2);
p1.X += ins[w];
return p1;
}
pll query(int a, int b) {
return query(a, b, 1, lv, 1);
}
};
int n, q;
ll w;
vector<pll> G[100007];
ii E[100007];
ll ecost[100007];
int p[100007], sz[100007];
int in[100007], out[100007];
int rein[100007];
int nxt_num = 1;
int first[100007];
SegmentSegmentTree paths(100007);
SegmentSegmentTree subtrees(100007);
void dfs(int w) {
sz[w] = 1;
for(auto u : G[w]) {
if(u.X != p[w]) {
p[u.X] = w;
dfs(u.X);
sz[w] += sz[u.X];
}
}
}
ll dfs2(int w, ll dist) {
for(auto &u : G[w])
if(sz[u.X] > sz[G[w][0].X])
swap(u, G[w][0]);
in[w] = out[w] = nxt_num++;
rein[in[w]] = w;
subtrees.initv(in[w], dist);
ll maxdist = dist, maxall = dist;
for(auto u : G[w]) {
if(u == G[w][0])
first[u.X] = first[w];
else
first[u.X] = u.X;
if(u != G[w][0])
maxdist = max(maxdist, dfs2(u.X, dist + u.Y));
else
maxall = max(maxall, dfs2(u.X, dist + u.Y));
out[w] = out[u.X];
}
//~ cout << w << " " << maxdist << endl;
maxall = max(maxall, maxdist);
paths.initv(in[w], maxdist - 2LL * dist);
return maxall;
}
ll longest_path() {
auto q = subtrees.query(1, n);
int w = rein[q.Y], pre = 0;
ll dw = q.X;
//~ cout << dw << " " << w << endl;
ll res = 0;
while(w) {
if(!pre || first[pre] == first[w]) {
res = max(res, paths.query(in[first[w]], in[w]).X + dw);
//~ cout << in[first[w]] << " " << in[w] << " " << w << " " << res << " " << paths.query(in[first[w]], in[w]).X << endl;
pre = first[w];
w = p[first[w]];
} else {
ll pdist = subtrees.query(in[w], in[w]).X;
res = max(res, subtrees.query(in[w], in[pre] - 1).X + dw - 2LL * pdist);
//~ cout << w << " " << pre << " " << pdist << " " << dw << " " << res << endl;
res = max(res, subtrees.query(out[pre] + 1, out[w]).X + dw - 2LL * pdist);
//~ cout << w << " " << pre << " " << pdist << " " << dw << " " << res << endl;
pre = w;
w = p[w];
}
}
return res;
}
void change_edge(int e, ll x) {
//~ cout << e << " " << x << endl;
int w = E[e].X;
int u = E[e].Y;
if(in[w] > in[u])
swap(w, u);
ll delta = x - ecost[e];
ecost[e] = x;
paths.insert(in[u], out[u], -delta);
subtrees.insert(in[u], out[u], delta);
w = p[first[u]];
//~ cout << w << " " << u << endl;
while(w) {
//~ cout << w << endl;
ll actv = paths.query(in[w], in[w]).X;
ll pdist = subtrees.query(in[w], in[w]).X;
ll newv = subtrees.query(out[G[w][0].X] + 1, out[w]).X - 2LL * pdist;
//~ cout << actv << " " << newv << endl;
paths.insert(in[w], in[w], newv - actv);
w = p[first[w]];
}
}
int main() {
scanf("%d%d%lld", &n, &q, &w);
for(int i = 1 ; i < n ; i++) {
int a, b;
ll c;
scanf("%d%d%lld", &a, &b, &c);
G[a].emplace_back(b, c);
G[b].emplace_back(a, c);
ecost[i] = c;
E[i] = {a, b};
}
dfs(1);
for(int i = 1 ; i <= n ; i++) {
for(int j = 0 ; j < G[i].size() ; j++) {
if(G[i][j].X == p[i]) {
G[i].erase(G[i].begin() + j);
break;
}
}
}
first[1] = 1;
dfs2(1, 0);
subtrees.process_init();
paths.process_init();
//~ for(int i = 1 ; i <= n ; i++)
//~ cout << i << " "<< first[i] << endl;
//~ cout << longest_path() << endl;
//~ cout << paths.query(1, 1).X << endl;
//~ for(int i = 1 ; i <= n ; i++)
//~ cout << i << " " << in[i] << " " << paths.query(in[i], in[i]).X << " " << paths.query(in[i], in[i]).Y << endl;
ll last = 0;
while(q--) {
ll d, e;
scanf("%lld%lld", &d, &e);
d = (d + last) % (n - 1);
e = (e + last) % w;
change_edge(d + 1, e);
//~ for(int i = 1 ; i <= n ; i++)
//~ cout << i << " " << in[i] << " " << paths.query(in[i], in[i]).X << " " << paths.query(in[i], in[i]).Y << endl;
printf("%lld\n", last = longest_path());
}
return 0;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:203:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < G[i].size() ; j++) {
~~^~~~~~~~~~~~~
diameter.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &n, &q, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:230:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &d, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14976 KB |
Output is correct |
2 |
Correct |
9 ms |
14976 KB |
Output is correct |
3 |
Correct |
11 ms |
15104 KB |
Output is correct |
4 |
Correct |
10 ms |
14976 KB |
Output is correct |
5 |
Correct |
10 ms |
14976 KB |
Output is correct |
6 |
Correct |
10 ms |
14976 KB |
Output is correct |
7 |
Correct |
10 ms |
15104 KB |
Output is correct |
8 |
Correct |
10 ms |
14976 KB |
Output is correct |
9 |
Correct |
10 ms |
15104 KB |
Output is correct |
10 |
Correct |
10 ms |
14976 KB |
Output is correct |
11 |
Correct |
10 ms |
14976 KB |
Output is correct |
12 |
Correct |
10 ms |
14976 KB |
Output is correct |
13 |
Correct |
10 ms |
15104 KB |
Output is correct |
14 |
Correct |
10 ms |
15104 KB |
Output is correct |
15 |
Correct |
10 ms |
14976 KB |
Output is correct |
16 |
Correct |
10 ms |
15104 KB |
Output is correct |
17 |
Correct |
10 ms |
15104 KB |
Output is correct |
18 |
Correct |
10 ms |
15104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14976 KB |
Output is correct |
2 |
Correct |
9 ms |
14976 KB |
Output is correct |
3 |
Correct |
11 ms |
15104 KB |
Output is correct |
4 |
Correct |
10 ms |
14976 KB |
Output is correct |
5 |
Correct |
10 ms |
14976 KB |
Output is correct |
6 |
Correct |
10 ms |
14976 KB |
Output is correct |
7 |
Correct |
10 ms |
15104 KB |
Output is correct |
8 |
Correct |
10 ms |
14976 KB |
Output is correct |
9 |
Correct |
10 ms |
15104 KB |
Output is correct |
10 |
Correct |
10 ms |
14976 KB |
Output is correct |
11 |
Correct |
10 ms |
14976 KB |
Output is correct |
12 |
Correct |
10 ms |
14976 KB |
Output is correct |
13 |
Correct |
10 ms |
15104 KB |
Output is correct |
14 |
Correct |
10 ms |
15104 KB |
Output is correct |
15 |
Correct |
10 ms |
14976 KB |
Output is correct |
16 |
Correct |
10 ms |
15104 KB |
Output is correct |
17 |
Correct |
10 ms |
15104 KB |
Output is correct |
18 |
Correct |
10 ms |
15104 KB |
Output is correct |
19 |
Correct |
39 ms |
15352 KB |
Output is correct |
20 |
Correct |
37 ms |
15232 KB |
Output is correct |
21 |
Correct |
29 ms |
15232 KB |
Output is correct |
22 |
Correct |
19 ms |
15232 KB |
Output is correct |
23 |
Correct |
49 ms |
15696 KB |
Output is correct |
24 |
Correct |
43 ms |
15616 KB |
Output is correct |
25 |
Correct |
31 ms |
15744 KB |
Output is correct |
26 |
Correct |
22 ms |
16128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14976 KB |
Output is correct |
2 |
Correct |
10 ms |
14976 KB |
Output is correct |
3 |
Correct |
15 ms |
15104 KB |
Output is correct |
4 |
Correct |
62 ms |
15232 KB |
Output is correct |
5 |
Correct |
279 ms |
15864 KB |
Output is correct |
6 |
Correct |
10 ms |
14976 KB |
Output is correct |
7 |
Correct |
9 ms |
15104 KB |
Output is correct |
8 |
Correct |
10 ms |
15104 KB |
Output is correct |
9 |
Correct |
16 ms |
15104 KB |
Output is correct |
10 |
Correct |
69 ms |
15352 KB |
Output is correct |
11 |
Correct |
334 ms |
15928 KB |
Output is correct |
12 |
Correct |
12 ms |
15488 KB |
Output is correct |
13 |
Correct |
12 ms |
15488 KB |
Output is correct |
14 |
Correct |
19 ms |
15616 KB |
Output is correct |
15 |
Correct |
87 ms |
15864 KB |
Output is correct |
16 |
Correct |
332 ms |
16376 KB |
Output is correct |
17 |
Correct |
56 ms |
24040 KB |
Output is correct |
18 |
Correct |
56 ms |
23984 KB |
Output is correct |
19 |
Correct |
69 ms |
24168 KB |
Output is correct |
20 |
Correct |
157 ms |
24040 KB |
Output is correct |
21 |
Correct |
451 ms |
24688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15104 KB |
Output is correct |
2 |
Correct |
79 ms |
15232 KB |
Output is correct |
3 |
Correct |
389 ms |
15788 KB |
Output is correct |
4 |
Correct |
729 ms |
16088 KB |
Output is correct |
5 |
Correct |
25 ms |
16128 KB |
Output is correct |
6 |
Correct |
127 ms |
16376 KB |
Output is correct |
7 |
Correct |
507 ms |
16632 KB |
Output is correct |
8 |
Correct |
1059 ms |
17808 KB |
Output is correct |
9 |
Correct |
55 ms |
20472 KB |
Output is correct |
10 |
Correct |
157 ms |
20668 KB |
Output is correct |
11 |
Correct |
694 ms |
21624 KB |
Output is correct |
12 |
Correct |
1283 ms |
22264 KB |
Output is correct |
13 |
Correct |
79 ms |
25976 KB |
Output is correct |
14 |
Correct |
202 ms |
26104 KB |
Output is correct |
15 |
Correct |
719 ms |
26744 KB |
Output is correct |
16 |
Correct |
1508 ms |
27872 KB |
Output is correct |
17 |
Correct |
2079 ms |
27512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1106 ms |
26172 KB |
Output is correct |
2 |
Correct |
1219 ms |
26232 KB |
Output is correct |
3 |
Correct |
1188 ms |
26104 KB |
Output is correct |
4 |
Correct |
1275 ms |
26112 KB |
Output is correct |
5 |
Correct |
1184 ms |
25956 KB |
Output is correct |
6 |
Correct |
1062 ms |
25708 KB |
Output is correct |
7 |
Correct |
679 ms |
29280 KB |
Output is correct |
8 |
Correct |
721 ms |
29084 KB |
Output is correct |
9 |
Correct |
553 ms |
29176 KB |
Output is correct |
10 |
Correct |
637 ms |
29176 KB |
Output is correct |
11 |
Correct |
642 ms |
28920 KB |
Output is correct |
12 |
Correct |
430 ms |
27884 KB |
Output is correct |
13 |
Correct |
336 ms |
34168 KB |
Output is correct |
14 |
Correct |
347 ms |
33784 KB |
Output is correct |
15 |
Correct |
350 ms |
33912 KB |
Output is correct |
16 |
Correct |
362 ms |
33784 KB |
Output is correct |
17 |
Correct |
403 ms |
33140 KB |
Output is correct |
18 |
Correct |
350 ms |
29548 KB |
Output is correct |
19 |
Correct |
345 ms |
34024 KB |
Output is correct |
20 |
Correct |
356 ms |
33784 KB |
Output is correct |
21 |
Correct |
341 ms |
33976 KB |
Output is correct |
22 |
Correct |
353 ms |
33784 KB |
Output is correct |
23 |
Correct |
357 ms |
33140 KB |
Output is correct |
24 |
Correct |
317 ms |
29596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14976 KB |
Output is correct |
2 |
Correct |
9 ms |
14976 KB |
Output is correct |
3 |
Correct |
11 ms |
15104 KB |
Output is correct |
4 |
Correct |
10 ms |
14976 KB |
Output is correct |
5 |
Correct |
10 ms |
14976 KB |
Output is correct |
6 |
Correct |
10 ms |
14976 KB |
Output is correct |
7 |
Correct |
10 ms |
15104 KB |
Output is correct |
8 |
Correct |
10 ms |
14976 KB |
Output is correct |
9 |
Correct |
10 ms |
15104 KB |
Output is correct |
10 |
Correct |
10 ms |
14976 KB |
Output is correct |
11 |
Correct |
10 ms |
14976 KB |
Output is correct |
12 |
Correct |
10 ms |
14976 KB |
Output is correct |
13 |
Correct |
10 ms |
15104 KB |
Output is correct |
14 |
Correct |
10 ms |
15104 KB |
Output is correct |
15 |
Correct |
10 ms |
14976 KB |
Output is correct |
16 |
Correct |
10 ms |
15104 KB |
Output is correct |
17 |
Correct |
10 ms |
15104 KB |
Output is correct |
18 |
Correct |
10 ms |
15104 KB |
Output is correct |
19 |
Correct |
39 ms |
15352 KB |
Output is correct |
20 |
Correct |
37 ms |
15232 KB |
Output is correct |
21 |
Correct |
29 ms |
15232 KB |
Output is correct |
22 |
Correct |
19 ms |
15232 KB |
Output is correct |
23 |
Correct |
49 ms |
15696 KB |
Output is correct |
24 |
Correct |
43 ms |
15616 KB |
Output is correct |
25 |
Correct |
31 ms |
15744 KB |
Output is correct |
26 |
Correct |
22 ms |
16128 KB |
Output is correct |
27 |
Correct |
10 ms |
14976 KB |
Output is correct |
28 |
Correct |
10 ms |
14976 KB |
Output is correct |
29 |
Correct |
15 ms |
15104 KB |
Output is correct |
30 |
Correct |
62 ms |
15232 KB |
Output is correct |
31 |
Correct |
279 ms |
15864 KB |
Output is correct |
32 |
Correct |
10 ms |
14976 KB |
Output is correct |
33 |
Correct |
9 ms |
15104 KB |
Output is correct |
34 |
Correct |
10 ms |
15104 KB |
Output is correct |
35 |
Correct |
16 ms |
15104 KB |
Output is correct |
36 |
Correct |
69 ms |
15352 KB |
Output is correct |
37 |
Correct |
334 ms |
15928 KB |
Output is correct |
38 |
Correct |
12 ms |
15488 KB |
Output is correct |
39 |
Correct |
12 ms |
15488 KB |
Output is correct |
40 |
Correct |
19 ms |
15616 KB |
Output is correct |
41 |
Correct |
87 ms |
15864 KB |
Output is correct |
42 |
Correct |
332 ms |
16376 KB |
Output is correct |
43 |
Correct |
56 ms |
24040 KB |
Output is correct |
44 |
Correct |
56 ms |
23984 KB |
Output is correct |
45 |
Correct |
69 ms |
24168 KB |
Output is correct |
46 |
Correct |
157 ms |
24040 KB |
Output is correct |
47 |
Correct |
451 ms |
24688 KB |
Output is correct |
48 |
Correct |
17 ms |
15104 KB |
Output is correct |
49 |
Correct |
79 ms |
15232 KB |
Output is correct |
50 |
Correct |
389 ms |
15788 KB |
Output is correct |
51 |
Correct |
729 ms |
16088 KB |
Output is correct |
52 |
Correct |
25 ms |
16128 KB |
Output is correct |
53 |
Correct |
127 ms |
16376 KB |
Output is correct |
54 |
Correct |
507 ms |
16632 KB |
Output is correct |
55 |
Correct |
1059 ms |
17808 KB |
Output is correct |
56 |
Correct |
55 ms |
20472 KB |
Output is correct |
57 |
Correct |
157 ms |
20668 KB |
Output is correct |
58 |
Correct |
694 ms |
21624 KB |
Output is correct |
59 |
Correct |
1283 ms |
22264 KB |
Output is correct |
60 |
Correct |
79 ms |
25976 KB |
Output is correct |
61 |
Correct |
202 ms |
26104 KB |
Output is correct |
62 |
Correct |
719 ms |
26744 KB |
Output is correct |
63 |
Correct |
1508 ms |
27872 KB |
Output is correct |
64 |
Correct |
2079 ms |
27512 KB |
Output is correct |
65 |
Correct |
1106 ms |
26172 KB |
Output is correct |
66 |
Correct |
1219 ms |
26232 KB |
Output is correct |
67 |
Correct |
1188 ms |
26104 KB |
Output is correct |
68 |
Correct |
1275 ms |
26112 KB |
Output is correct |
69 |
Correct |
1184 ms |
25956 KB |
Output is correct |
70 |
Correct |
1062 ms |
25708 KB |
Output is correct |
71 |
Correct |
679 ms |
29280 KB |
Output is correct |
72 |
Correct |
721 ms |
29084 KB |
Output is correct |
73 |
Correct |
553 ms |
29176 KB |
Output is correct |
74 |
Correct |
637 ms |
29176 KB |
Output is correct |
75 |
Correct |
642 ms |
28920 KB |
Output is correct |
76 |
Correct |
430 ms |
27884 KB |
Output is correct |
77 |
Correct |
336 ms |
34168 KB |
Output is correct |
78 |
Correct |
347 ms |
33784 KB |
Output is correct |
79 |
Correct |
350 ms |
33912 KB |
Output is correct |
80 |
Correct |
362 ms |
33784 KB |
Output is correct |
81 |
Correct |
403 ms |
33140 KB |
Output is correct |
82 |
Correct |
350 ms |
29548 KB |
Output is correct |
83 |
Correct |
345 ms |
34024 KB |
Output is correct |
84 |
Correct |
356 ms |
33784 KB |
Output is correct |
85 |
Correct |
341 ms |
33976 KB |
Output is correct |
86 |
Correct |
353 ms |
33784 KB |
Output is correct |
87 |
Correct |
357 ms |
33140 KB |
Output is correct |
88 |
Correct |
317 ms |
29596 KB |
Output is correct |
89 |
Correct |
1032 ms |
29048 KB |
Output is correct |
90 |
Correct |
886 ms |
29304 KB |
Output is correct |
91 |
Correct |
640 ms |
30840 KB |
Output is correct |
92 |
Correct |
639 ms |
30968 KB |
Output is correct |
93 |
Correct |
452 ms |
33628 KB |
Output is correct |
94 |
Correct |
551 ms |
32632 KB |
Output is correct |
95 |
Correct |
422 ms |
34428 KB |
Output is correct |
96 |
Correct |
443 ms |
33272 KB |
Output is correct |
97 |
Correct |
422 ms |
34296 KB |
Output is correct |
98 |
Correct |
364 ms |
36600 KB |
Output is correct |
99 |
Correct |
375 ms |
34168 KB |
Output is correct |
100 |
Correct |
371 ms |
34044 KB |
Output is correct |