#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll edge[100001], dp[100001], to_par[100001];
vector<pair<int, int>> graph[100001];
int par[100001], upper[100001], lower[100001];
multiset<ll> ms[100001], all;
void dfs(int node = 1, int parent = 0) {
par[node] = parent;
ms[node].insert(0);
for (pair<int, int> i : graph[node]) if (i.first != parent) {
upper[i.second] = node, lower[i.second] = i.first;
to_par[i.first] = i.second;
dfs(i.first, node);
ms[node].insert(dp[i.first] + edge[i.second]);
}
dp[node] = *ms[node].rbegin();
all.insert(dp[node] + *next(ms[node].rbegin()));
}
void propagate(int node, ll prv, ll curr) {
if (prv == curr) return;
ll par_prv = dp[node] + edge[to_par[node]];
all.erase(all.find(dp[node] + *next(ms[node].rbegin())));
ms[node].erase(ms[node].find(prv));
ms[node].insert(curr);
dp[node] = *ms[node].rbegin();
all.insert(dp[node] + *next(ms[node].rbegin()));
ll par_curr = dp[node] + edge[to_par[node]];
if (par[node]) propagate(par[node], par_prv, par_curr);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
ll w;
cin >> n >> q >> w;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v >> edge[i];
graph[u].push_back({v, i});
graph[v].push_back({u, i});
}
dfs();
ll last = 0;
while (q--) {
int d;
ll e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
propagate(upper[d], dp[lower[d]] + edge[d], dp[lower[d]] + e);
edge[d] = e;
last = *all.rbegin();
cout << last << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7532 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
6 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7532 KB |
Output is correct |
7 |
Correct |
6 ms |
7404 KB |
Output is correct |
8 |
Correct |
7 ms |
7404 KB |
Output is correct |
9 |
Correct |
6 ms |
7404 KB |
Output is correct |
10 |
Correct |
6 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
16 |
Correct |
6 ms |
7404 KB |
Output is correct |
17 |
Correct |
6 ms |
7404 KB |
Output is correct |
18 |
Correct |
7 ms |
7404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7532 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
6 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7532 KB |
Output is correct |
7 |
Correct |
6 ms |
7404 KB |
Output is correct |
8 |
Correct |
7 ms |
7404 KB |
Output is correct |
9 |
Correct |
6 ms |
7404 KB |
Output is correct |
10 |
Correct |
6 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
16 |
Correct |
6 ms |
7404 KB |
Output is correct |
17 |
Correct |
6 ms |
7404 KB |
Output is correct |
18 |
Correct |
7 ms |
7404 KB |
Output is correct |
19 |
Correct |
21 ms |
7788 KB |
Output is correct |
20 |
Correct |
40 ms |
7788 KB |
Output is correct |
21 |
Correct |
87 ms |
7788 KB |
Output is correct |
22 |
Correct |
291 ms |
7788 KB |
Output is correct |
23 |
Correct |
27 ms |
8704 KB |
Output is correct |
24 |
Correct |
89 ms |
8684 KB |
Output is correct |
25 |
Correct |
290 ms |
8824 KB |
Output is correct |
26 |
Correct |
3016 ms |
9332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
15 ms |
7660 KB |
Output is correct |
5 |
Correct |
54 ms |
8556 KB |
Output is correct |
6 |
Correct |
6 ms |
7404 KB |
Output is correct |
7 |
Correct |
6 ms |
7532 KB |
Output is correct |
8 |
Correct |
6 ms |
7532 KB |
Output is correct |
9 |
Correct |
8 ms |
7532 KB |
Output is correct |
10 |
Correct |
18 ms |
7788 KB |
Output is correct |
11 |
Correct |
65 ms |
8812 KB |
Output is correct |
12 |
Correct |
10 ms |
8556 KB |
Output is correct |
13 |
Correct |
13 ms |
8556 KB |
Output is correct |
14 |
Correct |
12 ms |
8556 KB |
Output is correct |
15 |
Correct |
26 ms |
8812 KB |
Output is correct |
16 |
Correct |
91 ms |
9964 KB |
Output is correct |
17 |
Correct |
150 ms |
30176 KB |
Output is correct |
18 |
Correct |
162 ms |
30304 KB |
Output is correct |
19 |
Correct |
159 ms |
30176 KB |
Output is correct |
20 |
Correct |
201 ms |
30432 KB |
Output is correct |
21 |
Correct |
461 ms |
31972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7660 KB |
Output is correct |
2 |
Correct |
19 ms |
7788 KB |
Output is correct |
3 |
Correct |
68 ms |
8432 KB |
Output is correct |
4 |
Correct |
130 ms |
9068 KB |
Output is correct |
5 |
Correct |
16 ms |
9708 KB |
Output is correct |
6 |
Correct |
33 ms |
9836 KB |
Output is correct |
7 |
Correct |
109 ms |
10476 KB |
Output is correct |
8 |
Correct |
197 ms |
11244 KB |
Output is correct |
9 |
Correct |
84 ms |
19180 KB |
Output is correct |
10 |
Correct |
119 ms |
19088 KB |
Output is correct |
11 |
Correct |
200 ms |
19852 KB |
Output is correct |
12 |
Correct |
409 ms |
20844 KB |
Output is correct |
13 |
Correct |
135 ms |
30572 KB |
Output is correct |
14 |
Correct |
164 ms |
30700 KB |
Output is correct |
15 |
Correct |
354 ms |
31596 KB |
Output is correct |
16 |
Correct |
490 ms |
32108 KB |
Output is correct |
17 |
Correct |
748 ms |
32052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1143 ms |
34412 KB |
Output is correct |
2 |
Correct |
1119 ms |
34488 KB |
Output is correct |
3 |
Correct |
1108 ms |
34636 KB |
Output is correct |
4 |
Correct |
1098 ms |
34412 KB |
Output is correct |
5 |
Correct |
1103 ms |
34464 KB |
Output is correct |
6 |
Correct |
949 ms |
34688 KB |
Output is correct |
7 |
Execution timed out |
5063 ms |
35176 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7532 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
6 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7532 KB |
Output is correct |
7 |
Correct |
6 ms |
7404 KB |
Output is correct |
8 |
Correct |
7 ms |
7404 KB |
Output is correct |
9 |
Correct |
6 ms |
7404 KB |
Output is correct |
10 |
Correct |
6 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
16 |
Correct |
6 ms |
7404 KB |
Output is correct |
17 |
Correct |
6 ms |
7404 KB |
Output is correct |
18 |
Correct |
7 ms |
7404 KB |
Output is correct |
19 |
Correct |
21 ms |
7788 KB |
Output is correct |
20 |
Correct |
40 ms |
7788 KB |
Output is correct |
21 |
Correct |
87 ms |
7788 KB |
Output is correct |
22 |
Correct |
291 ms |
7788 KB |
Output is correct |
23 |
Correct |
27 ms |
8704 KB |
Output is correct |
24 |
Correct |
89 ms |
8684 KB |
Output is correct |
25 |
Correct |
290 ms |
8824 KB |
Output is correct |
26 |
Correct |
3016 ms |
9332 KB |
Output is correct |
27 |
Correct |
6 ms |
7404 KB |
Output is correct |
28 |
Correct |
6 ms |
7404 KB |
Output is correct |
29 |
Correct |
6 ms |
7404 KB |
Output is correct |
30 |
Correct |
15 ms |
7660 KB |
Output is correct |
31 |
Correct |
54 ms |
8556 KB |
Output is correct |
32 |
Correct |
6 ms |
7404 KB |
Output is correct |
33 |
Correct |
6 ms |
7532 KB |
Output is correct |
34 |
Correct |
6 ms |
7532 KB |
Output is correct |
35 |
Correct |
8 ms |
7532 KB |
Output is correct |
36 |
Correct |
18 ms |
7788 KB |
Output is correct |
37 |
Correct |
65 ms |
8812 KB |
Output is correct |
38 |
Correct |
10 ms |
8556 KB |
Output is correct |
39 |
Correct |
13 ms |
8556 KB |
Output is correct |
40 |
Correct |
12 ms |
8556 KB |
Output is correct |
41 |
Correct |
26 ms |
8812 KB |
Output is correct |
42 |
Correct |
91 ms |
9964 KB |
Output is correct |
43 |
Correct |
150 ms |
30176 KB |
Output is correct |
44 |
Correct |
162 ms |
30304 KB |
Output is correct |
45 |
Correct |
159 ms |
30176 KB |
Output is correct |
46 |
Correct |
201 ms |
30432 KB |
Output is correct |
47 |
Correct |
461 ms |
31972 KB |
Output is correct |
48 |
Correct |
8 ms |
7660 KB |
Output is correct |
49 |
Correct |
19 ms |
7788 KB |
Output is correct |
50 |
Correct |
68 ms |
8432 KB |
Output is correct |
51 |
Correct |
130 ms |
9068 KB |
Output is correct |
52 |
Correct |
16 ms |
9708 KB |
Output is correct |
53 |
Correct |
33 ms |
9836 KB |
Output is correct |
54 |
Correct |
109 ms |
10476 KB |
Output is correct |
55 |
Correct |
197 ms |
11244 KB |
Output is correct |
56 |
Correct |
84 ms |
19180 KB |
Output is correct |
57 |
Correct |
119 ms |
19088 KB |
Output is correct |
58 |
Correct |
200 ms |
19852 KB |
Output is correct |
59 |
Correct |
409 ms |
20844 KB |
Output is correct |
60 |
Correct |
135 ms |
30572 KB |
Output is correct |
61 |
Correct |
164 ms |
30700 KB |
Output is correct |
62 |
Correct |
354 ms |
31596 KB |
Output is correct |
63 |
Correct |
490 ms |
32108 KB |
Output is correct |
64 |
Correct |
748 ms |
32052 KB |
Output is correct |
65 |
Correct |
1143 ms |
34412 KB |
Output is correct |
66 |
Correct |
1119 ms |
34488 KB |
Output is correct |
67 |
Correct |
1108 ms |
34636 KB |
Output is correct |
68 |
Correct |
1098 ms |
34412 KB |
Output is correct |
69 |
Correct |
1103 ms |
34464 KB |
Output is correct |
70 |
Correct |
949 ms |
34688 KB |
Output is correct |
71 |
Execution timed out |
5063 ms |
35176 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |