#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1 << 17, maxv = maxn * 2;
struct node
{
ll u, l, ul, lv, ulv, lazy; // premenne hovoria ze ktore vrcholy sme uz vybrali
int li, ri;
node() { u=l=ul=lv=ulv=lazy=0; }
} t[maxv * 2];
void merge(node &a, const node &l, const node &r)
{
a.u = max(l.u, r.u), a.l = max(l.l, r.l);
a.ul = max({l.ul, r.ul, l.u + r.l});
a.lv = max({l.lv, r.lv, l.l + r.u});
a.ulv = max({l.ulv, r.ulv, l.ul + r.u, l.u + r.lv});
}
void add(node &a, ll x)
{
a.u += x, a.l -= 2 * x;
a.ul -= x, a.lv -= x, a.lazy += x;
}
void unlazy(int vr)
{
add(t[vr * 2 + 1], t[vr].lazy), add(t[vr * 2 + 2], t[vr].lazy);
t[vr].lazy = 0;
}
void update(int l, int r, ll x, int vr = 0)
{
if (l > t[vr].ri || r < t[vr].li) return;
if (l <= t[vr].li && t[vr].ri <= r)
return add(t[vr], x), void();
unlazy(vr);
update(l, r, x, vr*2+1), update(l, r, x, vr*2+2);
merge(t[vr], t[vr*2+1], t[vr*2+2]);
}
struct edge { int u, v; ll x; } e[maxn];
int tin[maxn], tout[maxn], p[maxn], timer = 0; ll last = 0;
vector<int> g[maxn];
void dfs(int u)
{
tin[u] = timer++;
for (int i : g[u])
{
int v = u ^ e[i].u ^ e[i].v;
if (v == p[u]) continue;
if (u != e[i].u) swap(e[i].u, e[i].v);
p[v] = u; dfs(v); timer++;
}
tout[u] = timer-1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = maxv - 1; i < maxv * 2; i++) t[i].li = t[i].ri = i - (maxv - 1);
for (int i = maxv - 2; i >= 0; i--) t[i].li = t[i * 2 + 1].li, t[i].ri = t[i * 2 + 2].ri;
int n, q; ll w;
cin >> n >> q >> w;
for (int i = 0; i < n - 1; i++)
cin >> e[i].u >> e[i].v >> e[i].x, g[--e[i].u].push_back(i), g[--e[i].v].push_back(i);
dfs(0);
for (int i = 0; i < n - 1; i++)
update(tin[e[i].v], tout[e[i].v], e[i].x);
while (q--)
{
int i; ll wi; cin >> i >> wi;
i = ((ll)i + last) % (ll)(n-1), wi = (wi + last) % w;
update(tin[e[i].v], tout[e[i].v], wi - e[i].x);
e[i].x = wi;
cout << t[0].ulv << "\n";
last = t[0].ulv;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
32076 KB |
Output is correct |
2 |
Correct |
30 ms |
32124 KB |
Output is correct |
3 |
Correct |
23 ms |
32128 KB |
Output is correct |
4 |
Correct |
23 ms |
32076 KB |
Output is correct |
5 |
Correct |
24 ms |
32076 KB |
Output is correct |
6 |
Correct |
24 ms |
32076 KB |
Output is correct |
7 |
Correct |
24 ms |
32124 KB |
Output is correct |
8 |
Correct |
25 ms |
32128 KB |
Output is correct |
9 |
Correct |
26 ms |
32076 KB |
Output is correct |
10 |
Correct |
26 ms |
32024 KB |
Output is correct |
11 |
Correct |
25 ms |
32120 KB |
Output is correct |
12 |
Correct |
25 ms |
32028 KB |
Output is correct |
13 |
Correct |
26 ms |
32076 KB |
Output is correct |
14 |
Correct |
24 ms |
32128 KB |
Output is correct |
15 |
Correct |
26 ms |
32136 KB |
Output is correct |
16 |
Correct |
24 ms |
32092 KB |
Output is correct |
17 |
Correct |
25 ms |
32076 KB |
Output is correct |
18 |
Correct |
25 ms |
32076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
32076 KB |
Output is correct |
2 |
Correct |
30 ms |
32124 KB |
Output is correct |
3 |
Correct |
23 ms |
32128 KB |
Output is correct |
4 |
Correct |
23 ms |
32076 KB |
Output is correct |
5 |
Correct |
24 ms |
32076 KB |
Output is correct |
6 |
Correct |
24 ms |
32076 KB |
Output is correct |
7 |
Correct |
24 ms |
32124 KB |
Output is correct |
8 |
Correct |
25 ms |
32128 KB |
Output is correct |
9 |
Correct |
26 ms |
32076 KB |
Output is correct |
10 |
Correct |
26 ms |
32024 KB |
Output is correct |
11 |
Correct |
25 ms |
32120 KB |
Output is correct |
12 |
Correct |
25 ms |
32028 KB |
Output is correct |
13 |
Correct |
26 ms |
32076 KB |
Output is correct |
14 |
Correct |
24 ms |
32128 KB |
Output is correct |
15 |
Correct |
26 ms |
32136 KB |
Output is correct |
16 |
Correct |
24 ms |
32092 KB |
Output is correct |
17 |
Correct |
25 ms |
32076 KB |
Output is correct |
18 |
Correct |
25 ms |
32076 KB |
Output is correct |
19 |
Correct |
29 ms |
32268 KB |
Output is correct |
20 |
Correct |
29 ms |
32212 KB |
Output is correct |
21 |
Correct |
37 ms |
32216 KB |
Output is correct |
22 |
Correct |
30 ms |
32264 KB |
Output is correct |
23 |
Correct |
34 ms |
32500 KB |
Output is correct |
24 |
Correct |
36 ms |
32664 KB |
Output is correct |
25 |
Correct |
35 ms |
32572 KB |
Output is correct |
26 |
Correct |
47 ms |
32876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
32124 KB |
Output is correct |
2 |
Correct |
26 ms |
32124 KB |
Output is correct |
3 |
Correct |
28 ms |
32128 KB |
Output is correct |
4 |
Correct |
46 ms |
32272 KB |
Output is correct |
5 |
Correct |
111 ms |
33264 KB |
Output is correct |
6 |
Correct |
24 ms |
32076 KB |
Output is correct |
7 |
Correct |
25 ms |
32076 KB |
Output is correct |
8 |
Correct |
24 ms |
32132 KB |
Output is correct |
9 |
Correct |
29 ms |
32140 KB |
Output is correct |
10 |
Correct |
44 ms |
32324 KB |
Output is correct |
11 |
Correct |
109 ms |
33444 KB |
Output is correct |
12 |
Correct |
28 ms |
32460 KB |
Output is correct |
13 |
Correct |
29 ms |
32392 KB |
Output is correct |
14 |
Correct |
31 ms |
32504 KB |
Output is correct |
15 |
Correct |
49 ms |
32792 KB |
Output is correct |
16 |
Correct |
125 ms |
33868 KB |
Output is correct |
17 |
Correct |
120 ms |
39532 KB |
Output is correct |
18 |
Correct |
114 ms |
39604 KB |
Output is correct |
19 |
Correct |
119 ms |
39612 KB |
Output is correct |
20 |
Correct |
142 ms |
39868 KB |
Output is correct |
21 |
Correct |
358 ms |
41256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
32196 KB |
Output is correct |
2 |
Correct |
35 ms |
32276 KB |
Output is correct |
3 |
Correct |
76 ms |
32928 KB |
Output is correct |
4 |
Correct |
123 ms |
33588 KB |
Output is correct |
5 |
Correct |
36 ms |
32844 KB |
Output is correct |
6 |
Correct |
46 ms |
32964 KB |
Output is correct |
7 |
Correct |
94 ms |
33592 KB |
Output is correct |
8 |
Correct |
150 ms |
34372 KB |
Output is correct |
9 |
Correct |
85 ms |
35848 KB |
Output is correct |
10 |
Correct |
96 ms |
35960 KB |
Output is correct |
11 |
Correct |
148 ms |
36640 KB |
Output is correct |
12 |
Correct |
246 ms |
37480 KB |
Output is correct |
13 |
Correct |
136 ms |
39496 KB |
Output is correct |
14 |
Correct |
155 ms |
39696 KB |
Output is correct |
15 |
Correct |
223 ms |
40488 KB |
Output is correct |
16 |
Correct |
307 ms |
41180 KB |
Output is correct |
17 |
Correct |
330 ms |
40984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
43724 KB |
Output is correct |
2 |
Correct |
522 ms |
43604 KB |
Output is correct |
3 |
Correct |
487 ms |
43600 KB |
Output is correct |
4 |
Correct |
499 ms |
43668 KB |
Output is correct |
5 |
Correct |
462 ms |
43764 KB |
Output is correct |
6 |
Correct |
417 ms |
43972 KB |
Output is correct |
7 |
Correct |
520 ms |
46020 KB |
Output is correct |
8 |
Correct |
600 ms |
46016 KB |
Output is correct |
9 |
Correct |
562 ms |
45976 KB |
Output is correct |
10 |
Correct |
555 ms |
45952 KB |
Output is correct |
11 |
Correct |
555 ms |
45928 KB |
Output is correct |
12 |
Correct |
473 ms |
45700 KB |
Output is correct |
13 |
Correct |
654 ms |
49656 KB |
Output is correct |
14 |
Correct |
645 ms |
49768 KB |
Output is correct |
15 |
Correct |
623 ms |
49752 KB |
Output is correct |
16 |
Correct |
647 ms |
49812 KB |
Output is correct |
17 |
Correct |
679 ms |
49284 KB |
Output is correct |
18 |
Correct |
543 ms |
46956 KB |
Output is correct |
19 |
Correct |
727 ms |
49744 KB |
Output is correct |
20 |
Correct |
624 ms |
49744 KB |
Output is correct |
21 |
Correct |
663 ms |
49832 KB |
Output is correct |
22 |
Correct |
714 ms |
49796 KB |
Output is correct |
23 |
Correct |
728 ms |
49200 KB |
Output is correct |
24 |
Correct |
548 ms |
46944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
32076 KB |
Output is correct |
2 |
Correct |
30 ms |
32124 KB |
Output is correct |
3 |
Correct |
23 ms |
32128 KB |
Output is correct |
4 |
Correct |
23 ms |
32076 KB |
Output is correct |
5 |
Correct |
24 ms |
32076 KB |
Output is correct |
6 |
Correct |
24 ms |
32076 KB |
Output is correct |
7 |
Correct |
24 ms |
32124 KB |
Output is correct |
8 |
Correct |
25 ms |
32128 KB |
Output is correct |
9 |
Correct |
26 ms |
32076 KB |
Output is correct |
10 |
Correct |
26 ms |
32024 KB |
Output is correct |
11 |
Correct |
25 ms |
32120 KB |
Output is correct |
12 |
Correct |
25 ms |
32028 KB |
Output is correct |
13 |
Correct |
26 ms |
32076 KB |
Output is correct |
14 |
Correct |
24 ms |
32128 KB |
Output is correct |
15 |
Correct |
26 ms |
32136 KB |
Output is correct |
16 |
Correct |
24 ms |
32092 KB |
Output is correct |
17 |
Correct |
25 ms |
32076 KB |
Output is correct |
18 |
Correct |
25 ms |
32076 KB |
Output is correct |
19 |
Correct |
29 ms |
32268 KB |
Output is correct |
20 |
Correct |
29 ms |
32212 KB |
Output is correct |
21 |
Correct |
37 ms |
32216 KB |
Output is correct |
22 |
Correct |
30 ms |
32264 KB |
Output is correct |
23 |
Correct |
34 ms |
32500 KB |
Output is correct |
24 |
Correct |
36 ms |
32664 KB |
Output is correct |
25 |
Correct |
35 ms |
32572 KB |
Output is correct |
26 |
Correct |
47 ms |
32876 KB |
Output is correct |
27 |
Correct |
24 ms |
32124 KB |
Output is correct |
28 |
Correct |
26 ms |
32124 KB |
Output is correct |
29 |
Correct |
28 ms |
32128 KB |
Output is correct |
30 |
Correct |
46 ms |
32272 KB |
Output is correct |
31 |
Correct |
111 ms |
33264 KB |
Output is correct |
32 |
Correct |
24 ms |
32076 KB |
Output is correct |
33 |
Correct |
25 ms |
32076 KB |
Output is correct |
34 |
Correct |
24 ms |
32132 KB |
Output is correct |
35 |
Correct |
29 ms |
32140 KB |
Output is correct |
36 |
Correct |
44 ms |
32324 KB |
Output is correct |
37 |
Correct |
109 ms |
33444 KB |
Output is correct |
38 |
Correct |
28 ms |
32460 KB |
Output is correct |
39 |
Correct |
29 ms |
32392 KB |
Output is correct |
40 |
Correct |
31 ms |
32504 KB |
Output is correct |
41 |
Correct |
49 ms |
32792 KB |
Output is correct |
42 |
Correct |
125 ms |
33868 KB |
Output is correct |
43 |
Correct |
120 ms |
39532 KB |
Output is correct |
44 |
Correct |
114 ms |
39604 KB |
Output is correct |
45 |
Correct |
119 ms |
39612 KB |
Output is correct |
46 |
Correct |
142 ms |
39868 KB |
Output is correct |
47 |
Correct |
358 ms |
41256 KB |
Output is correct |
48 |
Correct |
27 ms |
32196 KB |
Output is correct |
49 |
Correct |
35 ms |
32276 KB |
Output is correct |
50 |
Correct |
76 ms |
32928 KB |
Output is correct |
51 |
Correct |
123 ms |
33588 KB |
Output is correct |
52 |
Correct |
36 ms |
32844 KB |
Output is correct |
53 |
Correct |
46 ms |
32964 KB |
Output is correct |
54 |
Correct |
94 ms |
33592 KB |
Output is correct |
55 |
Correct |
150 ms |
34372 KB |
Output is correct |
56 |
Correct |
85 ms |
35848 KB |
Output is correct |
57 |
Correct |
96 ms |
35960 KB |
Output is correct |
58 |
Correct |
148 ms |
36640 KB |
Output is correct |
59 |
Correct |
246 ms |
37480 KB |
Output is correct |
60 |
Correct |
136 ms |
39496 KB |
Output is correct |
61 |
Correct |
155 ms |
39696 KB |
Output is correct |
62 |
Correct |
223 ms |
40488 KB |
Output is correct |
63 |
Correct |
307 ms |
41180 KB |
Output is correct |
64 |
Correct |
330 ms |
40984 KB |
Output is correct |
65 |
Correct |
438 ms |
43724 KB |
Output is correct |
66 |
Correct |
522 ms |
43604 KB |
Output is correct |
67 |
Correct |
487 ms |
43600 KB |
Output is correct |
68 |
Correct |
499 ms |
43668 KB |
Output is correct |
69 |
Correct |
462 ms |
43764 KB |
Output is correct |
70 |
Correct |
417 ms |
43972 KB |
Output is correct |
71 |
Correct |
520 ms |
46020 KB |
Output is correct |
72 |
Correct |
600 ms |
46016 KB |
Output is correct |
73 |
Correct |
562 ms |
45976 KB |
Output is correct |
74 |
Correct |
555 ms |
45952 KB |
Output is correct |
75 |
Correct |
555 ms |
45928 KB |
Output is correct |
76 |
Correct |
473 ms |
45700 KB |
Output is correct |
77 |
Correct |
654 ms |
49656 KB |
Output is correct |
78 |
Correct |
645 ms |
49768 KB |
Output is correct |
79 |
Correct |
623 ms |
49752 KB |
Output is correct |
80 |
Correct |
647 ms |
49812 KB |
Output is correct |
81 |
Correct |
679 ms |
49284 KB |
Output is correct |
82 |
Correct |
543 ms |
46956 KB |
Output is correct |
83 |
Correct |
727 ms |
49744 KB |
Output is correct |
84 |
Correct |
624 ms |
49744 KB |
Output is correct |
85 |
Correct |
663 ms |
49832 KB |
Output is correct |
86 |
Correct |
714 ms |
49796 KB |
Output is correct |
87 |
Correct |
728 ms |
49200 KB |
Output is correct |
88 |
Correct |
548 ms |
46944 KB |
Output is correct |
89 |
Correct |
515 ms |
42704 KB |
Output is correct |
90 |
Correct |
489 ms |
43020 KB |
Output is correct |
91 |
Correct |
549 ms |
44268 KB |
Output is correct |
92 |
Correct |
524 ms |
44260 KB |
Output is correct |
93 |
Correct |
607 ms |
46404 KB |
Output is correct |
94 |
Correct |
547 ms |
45556 KB |
Output is correct |
95 |
Correct |
638 ms |
47164 KB |
Output is correct |
96 |
Correct |
752 ms |
46288 KB |
Output is correct |
97 |
Correct |
718 ms |
47044 KB |
Output is correct |
98 |
Correct |
738 ms |
48968 KB |
Output is correct |
99 |
Correct |
744 ms |
46904 KB |
Output is correct |
100 |
Correct |
713 ms |
46900 KB |
Output is correct |