#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
struct Edge {
ll w;
int a, b;
Edge() {}
Edge(ll w, int a, int b) : w(w), a(a), b(b) {}
int other(int x) const { return x == a ? b: a; }
};
vector<Edge*> graf[N];
Edge edges[N];
int centroid[N];
int cdepth[N];
int depth[18][N];
int droot[18][N];
int calc_size_and_number(int n, int f, int cd, int p, int d);
int decompose(int n, int f, int d) ;
multiset<ll, greater<ll>> centroid_subtree_depths[N];
void erase(multiset<ll, greater<ll>> &st, ll val) {
auto it = st.find(val);
if(it != st.end()) st.erase(it);
}
const int tree_size = 1 << 17;
//#define TS (tree_size >> min((qt - 1), 5))
#define TS tree_size
ll tree[18][2*tree_size];
ll lazy[18][2*tree_size];
int pre[18][N];
int post[18][N];
int ql, qr, qt;
ll qv;
ll add_tree(int n, int lms, int rms);
ll get_max(int n, int lms, int rms);
int main() {
ll n, q, w;
cin >> n >> q >> w;
for(int i = 0; i < n - 1; i++) {
scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
graf[edges[i].a].push_back(edges + i);
graf[edges[i].b].push_back(edges + i);
}
if(n == 2) {
ll last = 0;
while(q--) {
int edge_id;
ll new_weight;
scanf("%d%lld", &edge_id, &new_weight);
last = new_weight = (new_weight + last) % w;
printf("%lld\n", new_weight);
}
return 0;
}
auto t1 = chrono::high_resolution_clock::now();
calc_size_and_number(1, 0, 0, 1, 1);
int r = decompose(1, 0, 1);
centroid[r] = 0;
auto t2 = chrono::high_resolution_clock::now();
for(auto i = 0; i < n - 1; i++) {
Edge e = edges[i];
qv = e.w;
for(int j = 1; j <= 18; j++) {
if(!depth[j][e.a] || !depth[j][e.b]) break;
int x = depth[j][e.a] < depth[j][e.b] ? e.b : e.a;
qt = j;
ql = TS + pre[j][x];
qr = TS + post[j][x];
add_tree(1, TS, 2*TS - 1);
}
}
multiset<ll, greater<ll>> result;
auto t3 = chrono::high_resolution_clock::now();
for(auto v = 1; v <= n; v++) {
for(auto i: graf[v]) {
if(cdepth[i->other(v)] < cdepth[v]) continue;
qt = cdepth[v];
ql = pre[cdepth[v]][i->other(v)] + TS;
qr = post[cdepth[v]][i->other(v)] + TS;
ll x = get_max(1, TS, 2*TS - 1);
centroid_subtree_depths[v].insert(x);
}
if(centroid_subtree_depths[v].size() > 1)
result.insert(*centroid_subtree_depths[v].begin() + *++centroid_subtree_depths[v].begin());
}
auto t4 = chrono::high_resolution_clock::now();
/*
cout << "Phse 1: " << (double)(t2 - t1).count() / 1000000.0F << "ms" << endl;
cout << "Phse 2: " << (double)(t3 - t2).count() / 1000000.0F << "ms" << endl;
cout << "Phse 3: " << (double)(t4 - t3).count() / 1000000.0F << "ms" << endl;
*/
//return 0;
ll last = 0;
int mxd = 0;
while(q--) {
int edge_id;
ll new_weight;
scanf("%d%lld", &edge_id, &new_weight);
edge_id = (int)(((ll)edge_id + last) % (n - 1));
new_weight = (new_weight + last) % w;
Edge &e = edges[edge_id];
qv = new_weight - e.w;
int c = cdepth[e.a] < cdepth[e.b] ? e.a : e.b;
int cnt = 0;
while(c) {
if(centroid_subtree_depths[c].size() > 1) erase(result,*centroid_subtree_depths[c].begin() + *++centroid_subtree_depths[c].begin());
int d = cdepth[c];
int v = depth[d][e.a] < depth[d][e.b] ? e.b : e.a;
qt = d;
ql = pre[d][droot[d][v]] + TS;
qr = post[d][droot[d][v]] + TS;
ll x = get_max(1, TS, 2*TS - 1);
erase(centroid_subtree_depths[c], x);
ql = pre[d][v] + TS;
qr = post[d][v] + TS;
qv = new_weight - e.w;
add_tree(1, TS, 2*TS - 1);
ql = pre[d][droot[d][v]] + TS;
qr = post[d][droot[d][v]] + TS;
centroid_subtree_depths[c].insert(get_max(1, TS, 2*TS - 1));
if(centroid_subtree_depths[c].size() > 1) result.insert(*centroid_subtree_depths[c].begin() + *++centroid_subtree_depths[c].begin());
c = centroid[c];
cnt++;
}
e.w = new_weight;
last = *result.begin();
//cout << cnt << endl;
//mxd = max(mxd, cnt);
printf("%lld\n", last);
}
//cout << mxd << endl;
return 0;
}
void push_lazy(int t, int n) {
tree[t][n] += lazy[t][n];
if(n < TS) {
lazy[t][2 * n] += lazy[t][n];
lazy[t][2 * n + 1] += lazy[t][n];
}
lazy[t][n] = 0;
}
ll add_tree(int n, int lms, int rms) {
push_lazy(qt, n);
if(ql <= lms && rms <= qr) {
lazy[qt][n] += qv;
push_lazy(qt, n);
} else if(lms <= qr && ql <= rms) {
int m = (lms + rms) >> 1;
tree[qt][n] = max(add_tree(2*n, lms, m),
add_tree(2*n + 1, m + 1, rms));
}
return tree[qt][n];
}
ll get_max(int n, int lms, int rms) {
push_lazy(qt, n);
if(ql <= lms && rms <= qr) return tree[qt][n];
else if(lms <= qr && ql <= rms) {
int m = (lms + rms) >> 1;
return max(get_max(2*n, lms, m),
get_max(2*n + 1, m+ 1, rms));
}
return 0;
}
int sub_tree_size[N];
int last_num[20];
int calc_size_and_number(int n, int f, int cd, int p, int d) {
sub_tree_size[n] = 0;
post[cd][n] = pre[cd][n] = p;
depth[cd][n] = d;
for(auto i: graf[n]) {
if(i->other(n) == f || centroid[i->other(n)]) continue;
p = calc_size_and_number(i->other(n), n, cd, p + 1, d + 1);
sub_tree_size[n] += sub_tree_size[i->other(n)] + 1;
}
return post[cd][n] = p;
}
int find_centroid(int n, int root, int size, int f) {
for (auto i: graf[n]) {
if (i->other(n) == f || centroid[i->other(n)]) continue;
if (sub_tree_size[i->other(n)] >= size / 2)
return find_centroid(i->other(n), root, size, n);
}
return n;
}
void mark_droot(int n, int f, int cd, int r) {
droot[cd][n] = r;
for(auto i: graf[n]) {
if(i->other(n) == f || centroid[i->other(n)]) continue;
mark_droot(i->other(n), n, cd, r);
}
}
int decompose(int n, int f, int d) {
int r = find_centroid(n, f, sub_tree_size[n] + 1, 0);
centroid[r] = f ? f: r;
cdepth[r] = d;
last_num[d] = calc_size_and_number(r, 0, d, ++last_num[d], 1);
for(auto i: graf[r]) {
if(centroid[i->other(r)]) continue;
mark_droot(i->other(r), r, d, i->other(r));
decompose(i->other(r), r, d + 1);
}
return r;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:74:7: warning: variable 't1' set but not used [-Wunused-but-set-variable]
74 | auto t1 = chrono::high_resolution_clock::now();
| ^~
diameter.cpp:81:7: warning: variable 't2' set but not used [-Wunused-but-set-variable]
81 | auto t2 = chrono::high_resolution_clock::now();
| ^~
diameter.cpp:99:7: warning: variable 't3' set but not used [-Wunused-but-set-variable]
99 | auto t3 = chrono::high_resolution_clock::now();
| ^~
diameter.cpp:115:7: warning: variable 't4' set but not used [-Wunused-but-set-variable]
115 | auto t4 = chrono::high_resolution_clock::now();
| ^~
diameter.cpp:125:6: warning: unused variable 'mxd' [-Wunused-variable]
125 | int mxd = 0;
| ^~~
diameter.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%lld", &edge_id, &new_weight);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | scanf("%d%lld", &edge_id, &new_weight);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7636 KB |
Output is correct |
2 |
Correct |
4 ms |
7748 KB |
Output is correct |
3 |
Correct |
4 ms |
7636 KB |
Output is correct |
4 |
Correct |
4 ms |
7636 KB |
Output is correct |
5 |
Correct |
4 ms |
7764 KB |
Output is correct |
6 |
Correct |
4 ms |
7636 KB |
Output is correct |
7 |
Correct |
5 ms |
7764 KB |
Output is correct |
8 |
Correct |
4 ms |
7892 KB |
Output is correct |
9 |
Correct |
4 ms |
7892 KB |
Output is correct |
10 |
Correct |
4 ms |
7892 KB |
Output is correct |
11 |
Correct |
5 ms |
7876 KB |
Output is correct |
12 |
Correct |
4 ms |
7892 KB |
Output is correct |
13 |
Correct |
4 ms |
7892 KB |
Output is correct |
14 |
Correct |
5 ms |
7880 KB |
Output is correct |
15 |
Correct |
4 ms |
7868 KB |
Output is correct |
16 |
Correct |
5 ms |
7892 KB |
Output is correct |
17 |
Correct |
5 ms |
8020 KB |
Output is correct |
18 |
Correct |
5 ms |
8020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7636 KB |
Output is correct |
2 |
Correct |
4 ms |
7748 KB |
Output is correct |
3 |
Correct |
4 ms |
7636 KB |
Output is correct |
4 |
Correct |
4 ms |
7636 KB |
Output is correct |
5 |
Correct |
4 ms |
7764 KB |
Output is correct |
6 |
Correct |
4 ms |
7636 KB |
Output is correct |
7 |
Correct |
5 ms |
7764 KB |
Output is correct |
8 |
Correct |
4 ms |
7892 KB |
Output is correct |
9 |
Correct |
4 ms |
7892 KB |
Output is correct |
10 |
Correct |
4 ms |
7892 KB |
Output is correct |
11 |
Correct |
5 ms |
7876 KB |
Output is correct |
12 |
Correct |
4 ms |
7892 KB |
Output is correct |
13 |
Correct |
4 ms |
7892 KB |
Output is correct |
14 |
Correct |
5 ms |
7880 KB |
Output is correct |
15 |
Correct |
4 ms |
7868 KB |
Output is correct |
16 |
Correct |
5 ms |
7892 KB |
Output is correct |
17 |
Correct |
5 ms |
8020 KB |
Output is correct |
18 |
Correct |
5 ms |
8020 KB |
Output is correct |
19 |
Correct |
41 ms |
8656 KB |
Output is correct |
20 |
Correct |
45 ms |
8780 KB |
Output is correct |
21 |
Correct |
55 ms |
8820 KB |
Output is correct |
22 |
Correct |
65 ms |
8888 KB |
Output is correct |
23 |
Correct |
67 ms |
10696 KB |
Output is correct |
24 |
Correct |
96 ms |
11440 KB |
Output is correct |
25 |
Correct |
102 ms |
11780 KB |
Output is correct |
26 |
Correct |
122 ms |
12256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7508 KB |
Output is correct |
2 |
Correct |
4 ms |
7468 KB |
Output is correct |
3 |
Correct |
7 ms |
7500 KB |
Output is correct |
4 |
Correct |
28 ms |
7720 KB |
Output is correct |
5 |
Correct |
121 ms |
8572 KB |
Output is correct |
6 |
Correct |
4 ms |
7252 KB |
Output is correct |
7 |
Correct |
4 ms |
7508 KB |
Output is correct |
8 |
Correct |
4 ms |
7508 KB |
Output is correct |
9 |
Correct |
7 ms |
7636 KB |
Output is correct |
10 |
Correct |
30 ms |
7852 KB |
Output is correct |
11 |
Correct |
136 ms |
9044 KB |
Output is correct |
12 |
Correct |
9 ms |
8404 KB |
Output is correct |
13 |
Correct |
10 ms |
8400 KB |
Output is correct |
14 |
Correct |
12 ms |
8396 KB |
Output is correct |
15 |
Correct |
39 ms |
8684 KB |
Output is correct |
16 |
Correct |
151 ms |
9784 KB |
Output is correct |
17 |
Correct |
124 ms |
26940 KB |
Output is correct |
18 |
Correct |
123 ms |
26988 KB |
Output is correct |
19 |
Correct |
128 ms |
27032 KB |
Output is correct |
20 |
Correct |
167 ms |
27360 KB |
Output is correct |
21 |
Correct |
371 ms |
28672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
8660 KB |
Output is correct |
2 |
Correct |
75 ms |
8788 KB |
Output is correct |
3 |
Correct |
321 ms |
9296 KB |
Output is correct |
4 |
Correct |
652 ms |
10068 KB |
Output is correct |
5 |
Correct |
69 ms |
15128 KB |
Output is correct |
6 |
Correct |
156 ms |
15216 KB |
Output is correct |
7 |
Correct |
572 ms |
15972 KB |
Output is correct |
8 |
Correct |
1054 ms |
16820 KB |
Output is correct |
9 |
Correct |
365 ms |
48024 KB |
Output is correct |
10 |
Correct |
513 ms |
48280 KB |
Output is correct |
11 |
Correct |
1115 ms |
48788 KB |
Output is correct |
12 |
Correct |
1895 ms |
49672 KB |
Output is correct |
13 |
Correct |
772 ms |
92260 KB |
Output is correct |
14 |
Correct |
921 ms |
92232 KB |
Output is correct |
15 |
Correct |
1668 ms |
92996 KB |
Output is correct |
16 |
Correct |
2509 ms |
93776 KB |
Output is correct |
17 |
Correct |
4546 ms |
93684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3741 ms |
84924 KB |
Output is correct |
2 |
Correct |
3895 ms |
86604 KB |
Output is correct |
3 |
Correct |
3897 ms |
85220 KB |
Output is correct |
4 |
Correct |
3967 ms |
87312 KB |
Output is correct |
5 |
Correct |
3820 ms |
83200 KB |
Output is correct |
6 |
Correct |
3487 ms |
71000 KB |
Output is correct |
7 |
Execution timed out |
5099 ms |
102100 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7636 KB |
Output is correct |
2 |
Correct |
4 ms |
7748 KB |
Output is correct |
3 |
Correct |
4 ms |
7636 KB |
Output is correct |
4 |
Correct |
4 ms |
7636 KB |
Output is correct |
5 |
Correct |
4 ms |
7764 KB |
Output is correct |
6 |
Correct |
4 ms |
7636 KB |
Output is correct |
7 |
Correct |
5 ms |
7764 KB |
Output is correct |
8 |
Correct |
4 ms |
7892 KB |
Output is correct |
9 |
Correct |
4 ms |
7892 KB |
Output is correct |
10 |
Correct |
4 ms |
7892 KB |
Output is correct |
11 |
Correct |
5 ms |
7876 KB |
Output is correct |
12 |
Correct |
4 ms |
7892 KB |
Output is correct |
13 |
Correct |
4 ms |
7892 KB |
Output is correct |
14 |
Correct |
5 ms |
7880 KB |
Output is correct |
15 |
Correct |
4 ms |
7868 KB |
Output is correct |
16 |
Correct |
5 ms |
7892 KB |
Output is correct |
17 |
Correct |
5 ms |
8020 KB |
Output is correct |
18 |
Correct |
5 ms |
8020 KB |
Output is correct |
19 |
Correct |
41 ms |
8656 KB |
Output is correct |
20 |
Correct |
45 ms |
8780 KB |
Output is correct |
21 |
Correct |
55 ms |
8820 KB |
Output is correct |
22 |
Correct |
65 ms |
8888 KB |
Output is correct |
23 |
Correct |
67 ms |
10696 KB |
Output is correct |
24 |
Correct |
96 ms |
11440 KB |
Output is correct |
25 |
Correct |
102 ms |
11780 KB |
Output is correct |
26 |
Correct |
122 ms |
12256 KB |
Output is correct |
27 |
Correct |
4 ms |
7508 KB |
Output is correct |
28 |
Correct |
4 ms |
7468 KB |
Output is correct |
29 |
Correct |
7 ms |
7500 KB |
Output is correct |
30 |
Correct |
28 ms |
7720 KB |
Output is correct |
31 |
Correct |
121 ms |
8572 KB |
Output is correct |
32 |
Correct |
4 ms |
7252 KB |
Output is correct |
33 |
Correct |
4 ms |
7508 KB |
Output is correct |
34 |
Correct |
4 ms |
7508 KB |
Output is correct |
35 |
Correct |
7 ms |
7636 KB |
Output is correct |
36 |
Correct |
30 ms |
7852 KB |
Output is correct |
37 |
Correct |
136 ms |
9044 KB |
Output is correct |
38 |
Correct |
9 ms |
8404 KB |
Output is correct |
39 |
Correct |
10 ms |
8400 KB |
Output is correct |
40 |
Correct |
12 ms |
8396 KB |
Output is correct |
41 |
Correct |
39 ms |
8684 KB |
Output is correct |
42 |
Correct |
151 ms |
9784 KB |
Output is correct |
43 |
Correct |
124 ms |
26940 KB |
Output is correct |
44 |
Correct |
123 ms |
26988 KB |
Output is correct |
45 |
Correct |
128 ms |
27032 KB |
Output is correct |
46 |
Correct |
167 ms |
27360 KB |
Output is correct |
47 |
Correct |
371 ms |
28672 KB |
Output is correct |
48 |
Correct |
15 ms |
8660 KB |
Output is correct |
49 |
Correct |
75 ms |
8788 KB |
Output is correct |
50 |
Correct |
321 ms |
9296 KB |
Output is correct |
51 |
Correct |
652 ms |
10068 KB |
Output is correct |
52 |
Correct |
69 ms |
15128 KB |
Output is correct |
53 |
Correct |
156 ms |
15216 KB |
Output is correct |
54 |
Correct |
572 ms |
15972 KB |
Output is correct |
55 |
Correct |
1054 ms |
16820 KB |
Output is correct |
56 |
Correct |
365 ms |
48024 KB |
Output is correct |
57 |
Correct |
513 ms |
48280 KB |
Output is correct |
58 |
Correct |
1115 ms |
48788 KB |
Output is correct |
59 |
Correct |
1895 ms |
49672 KB |
Output is correct |
60 |
Correct |
772 ms |
92260 KB |
Output is correct |
61 |
Correct |
921 ms |
92232 KB |
Output is correct |
62 |
Correct |
1668 ms |
92996 KB |
Output is correct |
63 |
Correct |
2509 ms |
93776 KB |
Output is correct |
64 |
Correct |
4546 ms |
93684 KB |
Output is correct |
65 |
Correct |
3741 ms |
84924 KB |
Output is correct |
66 |
Correct |
3895 ms |
86604 KB |
Output is correct |
67 |
Correct |
3897 ms |
85220 KB |
Output is correct |
68 |
Correct |
3967 ms |
87312 KB |
Output is correct |
69 |
Correct |
3820 ms |
83200 KB |
Output is correct |
70 |
Correct |
3487 ms |
71000 KB |
Output is correct |
71 |
Execution timed out |
5099 ms |
102100 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |