#include <bits/stdc++.h>
using namespace std;
class Solver {
using wgt = long long;
class IntervalTree {
using wgt = long long;
static constexpr wgt no_val = -(1LL<<60);
struct node {
wgt val, add;
};
int b;
vector<node> T;
inline __attribute__((always_inline)) void upd(int i, bool leaf) {
wgt add = T[i].add;
if(add == 0) return;
T[i].val += add;
T[i].add = 0;
if(!leaf) {
T[2*i].add += add;
T[2*i+1].add += add;
}
}
void get_internal(int l, int r, int i, int n_l, int n_r, wgt & max_val) {
if(n_l >= r || l >= n_r) return;
upd(i, n_l+1 == n_r);
if((n_l == l && n_r == r) || T[i].val <= max_val) {
max_val = max(max_val, T[i].val);
return;
}
int c = (n_l + n_r) / 2;
get_internal(l, min(r, c), 2*i, n_l, c, max_val);
get_internal(max(l, c), r, 2*i+1, c, n_r, max_val);
}
public:
IntervalTree() {}
IntervalTree(int N) {
b = 1;
while(b < N) b *= 2;
T.resize(2*b+1, {0, 0});
}
void add(int l, int r, wgt w_add, int i = 1, int n_l = 0, int n_r = 0) {
if(i == 1) n_r = b;
if(n_l == l && n_r == r) {
T[i].add += w_add;
upd(i, n_l+1 == n_r);
return;
}
upd(i, n_l+1 == n_r);
if(n_l >= r || l >= n_r) return;
int c = (n_l + n_r) / 2;
add(l, min(r, c), w_add, 2*i, n_l, c);
add(max(l, c), r, w_add, 2*i+1, c, n_r);
T[i].val = max(T[2*i].val, T[2*i+1].val);
}
void put(int pos, wgt w, int i = 1, int n_l = 0, int n_r = 0) {
if(i == 1) n_r = b;
if(n_l == pos && n_r == pos+1) {
T[i].val = w;
T[i].add = 0;
return;
}
upd(i, n_l+1 == n_r);
if(n_l > pos || pos >= n_r) return;
int c = (n_l + n_r) / 2;
if(pos < c) {
upd(2*i+1, c+1 == n_r);
put(pos, w, 2*i, n_l, c);
}
else {
upd(2*i, n_l+1 == c);
put(pos, w, 2*i+1, c, n_r);
}
T[i].val = max(T[2*i].val, T[2*i+1].val);
}
pair<wgt, int> get(int l, int r, bool with_id = false) { // max [l..r)
wgt ret = no_val;
get_internal(l, r, 1, 0, b, ret);
if(!with_id) return {ret, 0};
int cur = 1, n_l = 0, n_r = b;
while(n_l+1 != n_r) {
int c = (n_l + n_r) / 2;
upd(2*cur, n_l+1 == c);
if(T[2*cur].val == ret) {
cur = 2*cur;
n_r = c;
}
else {
upd(2*cur+1, c+1 == n_r);
n_l = c;
cur = 2*cur+1;
}
}
return {ret, n_l};
}
wgt get_pos(int pos) { // max [pos]
int cur = 1, n_l = 0, n_r = b;
while(true) {
upd(cur, n_l+1 == n_r);
if(n_l+1 == n_r) {
return T[cur].val;
break;
}
int c = (n_l + n_r) / 2;
if(pos < c) {
n_r = c;
cur = 2*cur;
}
else {
n_l = c;
cur = 2*cur+1;
}
}
return no_val;
}
};
int N, R, P; // R = root, P = number of paths
vector<int> par;
vector< vector<int> > G; // sons
vector< pair<int, int> > interval_renumbering;
vector<int> v_from_interval_id;
vector<int> subtree_size;
vector< vector<int> > paths;
vector<int> path_id, path_pos; // paths[path_id[i]][path_pos[i]] == i
vector< vector< vector< pair<int, int> > > > down_edges; // light edges (child, index in tree) + dummy self-loops
vector<int> down_edge_id;
vector< vector<int> > last_down_edge; // largest index of light edge from (parent) + 1
vector<wgt> W;
IntervalTree max_dist_down;
vector<IntervalTree> tree_over_path;
void DFS_construct(int v, const vector< vector< pair<int, wgt> > > & G_) {
interval_renumbering[v].second = interval_renumbering[v].first+1;
v_from_interval_id[interval_renumbering[v].first] = v;
subtree_size[v] = 1;
int max_subtree_size = 0, son_in_path = -1;
for(auto p : G_[v]) if(par[p.first] == -1) {
int w = p.first;
par[w] = v;
G[v].push_back(w);
W[w] = p.second;
interval_renumbering[w].first = interval_renumbering[v].second;
DFS_construct(w, G_);
interval_renumbering[v].second = interval_renumbering[w].second;
max_dist_down.add(interval_renumbering[w].first, interval_renumbering[w].second, p.second);
subtree_size[v] += subtree_size[w];
if(subtree_size[w] > max_subtree_size) {
max_subtree_size = subtree_size[w];
son_in_path = w;
}
}
if(son_in_path == -1) {
path_id[v] = P++;
paths.push_back({});
}
else path_id[v] = path_id[son_in_path];
paths[path_id[v]].push_back(v);
}
wgt get_max_dist_down(int v) {
return max_dist_down.get(interval_renumbering[v].first, interval_renumbering[v].second).first;
}
wgt get_dep(int v) {
return max_dist_down.get_pos(interval_renumbering[v].first);
}
public:
Solver(vector< vector< pair<int, wgt> > > & G_) : N(G_.size()), R(0), P(0) {
par.resize(N, -1);
G.resize(N);
interval_renumbering.resize(N, {0, 0});
subtree_size.resize(N);
path_id.resize(N);
path_pos.resize(N);
W.resize(N, 0);
v_from_interval_id.resize(N);
max_dist_down = IntervalTree(N);
par[R] = R;
DFS_construct(R, G_);
for(int i = 0; i < P; i++) reverse(begin(paths[i]), end(paths[i]));
tree_over_path.resize(P);
down_edges.resize(P);
last_down_edge.resize(P);
down_edge_id.resize(N);
for(int i = 0; i < P; i++) {
int num_edges = 0, L = paths[i].size();
down_edges[i].resize(L);
last_down_edge[i].resize(L);
for(int j = 0; j < L; j++) {
path_pos[paths[i][j]] = j;
for(auto son : G[paths[i][j]]) if(path_id[son] != i) {
down_edge_id[son] = num_edges;
down_edges[i][j].push_back({son, num_edges++});
}
down_edges[i][j].push_back({paths[i][j], num_edges++});
last_down_edge[i][j] = num_edges;
}
tree_over_path[i] = IntervalTree(num_edges);
wgt dist_from_top = 0;
for(int j = 0; j < L; j++) {
if(j > 0) dist_from_top += W[paths[i][j]];
for(auto edge : down_edges[i][j]) {
wgt val = 0;
if(edge.first != paths[i][j])
val = get_max_dist_down(edge.first) - get_dep(edge.first) + W[edge.first];
tree_over_path[i].put(edge.second, val - dist_from_top);
}
}
}
}
void update(int u, int v, wgt w) {
if(par[u] == v) swap(u, v);
// update weight(par[v]--v) to w
max_dist_down.add(interval_renumbering[v].first, interval_renumbering[v].second, w-W[v]);
if(path_id[v] == path_id[u])
tree_over_path[path_id[v]].add(last_down_edge[path_id[u]][path_pos[u]], last_down_edge[path_id[u]].back(), W[v]-w);
W[v] = w;
v = paths[path_id[v]][0];
while(v != R) {
int v_old = v;
v = par[v];
int r = last_down_edge[path_id[v]][path_pos[v]];
wgt dist_from_top = -tree_over_path[path_id[v]].get_pos(r-1);
tree_over_path[path_id[v]].put(down_edge_id[v_old], get_max_dist_down(v_old) - get_dep(v) - dist_from_top);
v = paths[path_id[v]][0];
}
}
wgt query() {
// return diameter
pair<wgt, int> p = max_dist_down.get(0, N, true);
int v = v_from_interval_id[p.second];
wgt ret = p.first, dist_up = 0;
int last_edge_id = -1;
while(true) {
int r = last_down_edge[path_id[v]][path_pos[v]];
wgt dist_from_top = -tree_over_path[path_id[v]].get_pos(r-1);
ret = max(ret, dist_up + dist_from_top + tree_over_path[path_id[v]].get(0, last_edge_id).first);
ret = max(ret, dist_up + dist_from_top + tree_over_path[path_id[v]].get(last_edge_id+1, r).first);
if(path_pos[v]+1 < (int)paths[path_id[v]].size())
ret = max(ret, dist_up + get_max_dist_down(paths[path_id[v]][path_pos[v]+1]) - get_dep(v));
dist_up += dist_from_top;
v = paths[path_id[v]][0];
if(v == R) break;
last_edge_id = down_edge_id[v];
dist_up += W[v];
v = par[v];
}
return ret;
}
};
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int N, Q;
long long W;
cin >> N >> Q >> W;
vector< pair<int, int> > E(N-1);
vector< vector< pair<int, long long> > > G(N);
for(int i = 0; i < N-1; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
G[--u].push_back({--v, w});
G[v].push_back({u, w});
E[i] = {u, v};
}
Solver solver(G);
long long last = 0;
for(int i = 0; i < Q; i++) {
long long e, w;
cin >> e >> w;
e = (e + last) % (N-1);
w = (w + last) % W;
int u = E[e].first, v = E[e].second;
solver.update(u, v, w);
last = solver.query();
cout << last << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
16 ms |
760 KB |
Output is correct |
20 |
Correct |
15 ms |
760 KB |
Output is correct |
21 |
Correct |
14 ms |
820 KB |
Output is correct |
22 |
Correct |
10 ms |
760 KB |
Output is correct |
23 |
Correct |
32 ms |
2556 KB |
Output is correct |
24 |
Correct |
27 ms |
2424 KB |
Output is correct |
25 |
Correct |
23 ms |
2580 KB |
Output is correct |
26 |
Correct |
18 ms |
3004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
19 ms |
456 KB |
Output is correct |
5 |
Correct |
83 ms |
732 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
3 ms |
632 KB |
Output is correct |
8 |
Correct |
3 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
632 KB |
Output is correct |
10 |
Correct |
29 ms |
764 KB |
Output is correct |
11 |
Correct |
135 ms |
1008 KB |
Output is correct |
12 |
Correct |
11 ms |
3096 KB |
Output is correct |
13 |
Correct |
12 ms |
3108 KB |
Output is correct |
14 |
Correct |
14 ms |
3064 KB |
Output is correct |
15 |
Correct |
47 ms |
3192 KB |
Output is correct |
16 |
Correct |
200 ms |
3680 KB |
Output is correct |
17 |
Correct |
192 ms |
52836 KB |
Output is correct |
18 |
Correct |
190 ms |
52792 KB |
Output is correct |
19 |
Correct |
199 ms |
52836 KB |
Output is correct |
20 |
Correct |
251 ms |
52900 KB |
Output is correct |
21 |
Correct |
499 ms |
53476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
760 KB |
Output is correct |
2 |
Correct |
30 ms |
760 KB |
Output is correct |
3 |
Correct |
134 ms |
1000 KB |
Output is correct |
4 |
Correct |
263 ms |
1400 KB |
Output is correct |
5 |
Correct |
29 ms |
4728 KB |
Output is correct |
6 |
Correct |
67 ms |
4856 KB |
Output is correct |
7 |
Correct |
258 ms |
4984 KB |
Output is correct |
8 |
Correct |
507 ms |
5584 KB |
Output is correct |
9 |
Correct |
110 ms |
21680 KB |
Output is correct |
10 |
Correct |
163 ms |
21752 KB |
Output is correct |
11 |
Correct |
422 ms |
22280 KB |
Output is correct |
12 |
Correct |
731 ms |
22448 KB |
Output is correct |
13 |
Correct |
213 ms |
43112 KB |
Output is correct |
14 |
Correct |
298 ms |
43180 KB |
Output is correct |
15 |
Correct |
609 ms |
43684 KB |
Output is correct |
16 |
Correct |
1024 ms |
44132 KB |
Output is correct |
17 |
Correct |
1354 ms |
43816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
916 ms |
42744 KB |
Output is correct |
2 |
Correct |
948 ms |
42524 KB |
Output is correct |
3 |
Correct |
1077 ms |
42640 KB |
Output is correct |
4 |
Correct |
958 ms |
42864 KB |
Output is correct |
5 |
Correct |
937 ms |
43944 KB |
Output is correct |
6 |
Correct |
866 ms |
48612 KB |
Output is correct |
7 |
Correct |
742 ms |
46332 KB |
Output is correct |
8 |
Correct |
716 ms |
46084 KB |
Output is correct |
9 |
Correct |
720 ms |
46508 KB |
Output is correct |
10 |
Correct |
697 ms |
46348 KB |
Output is correct |
11 |
Correct |
739 ms |
46988 KB |
Output is correct |
12 |
Correct |
594 ms |
51708 KB |
Output is correct |
13 |
Correct |
575 ms |
49592 KB |
Output is correct |
14 |
Correct |
650 ms |
49552 KB |
Output is correct |
15 |
Correct |
546 ms |
49592 KB |
Output is correct |
16 |
Correct |
544 ms |
49596 KB |
Output is correct |
17 |
Correct |
525 ms |
50004 KB |
Output is correct |
18 |
Correct |
496 ms |
51924 KB |
Output is correct |
19 |
Correct |
509 ms |
49472 KB |
Output is correct |
20 |
Correct |
512 ms |
49608 KB |
Output is correct |
21 |
Correct |
537 ms |
49524 KB |
Output is correct |
22 |
Correct |
536 ms |
49728 KB |
Output is correct |
23 |
Correct |
552 ms |
50092 KB |
Output is correct |
24 |
Correct |
513 ms |
51816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
16 ms |
760 KB |
Output is correct |
20 |
Correct |
15 ms |
760 KB |
Output is correct |
21 |
Correct |
14 ms |
820 KB |
Output is correct |
22 |
Correct |
10 ms |
760 KB |
Output is correct |
23 |
Correct |
32 ms |
2556 KB |
Output is correct |
24 |
Correct |
27 ms |
2424 KB |
Output is correct |
25 |
Correct |
23 ms |
2580 KB |
Output is correct |
26 |
Correct |
18 ms |
3004 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
4 ms |
376 KB |
Output is correct |
30 |
Correct |
19 ms |
456 KB |
Output is correct |
31 |
Correct |
83 ms |
732 KB |
Output is correct |
32 |
Correct |
2 ms |
380 KB |
Output is correct |
33 |
Correct |
3 ms |
632 KB |
Output is correct |
34 |
Correct |
3 ms |
632 KB |
Output is correct |
35 |
Correct |
5 ms |
632 KB |
Output is correct |
36 |
Correct |
29 ms |
764 KB |
Output is correct |
37 |
Correct |
135 ms |
1008 KB |
Output is correct |
38 |
Correct |
11 ms |
3096 KB |
Output is correct |
39 |
Correct |
12 ms |
3108 KB |
Output is correct |
40 |
Correct |
14 ms |
3064 KB |
Output is correct |
41 |
Correct |
47 ms |
3192 KB |
Output is correct |
42 |
Correct |
200 ms |
3680 KB |
Output is correct |
43 |
Correct |
192 ms |
52836 KB |
Output is correct |
44 |
Correct |
190 ms |
52792 KB |
Output is correct |
45 |
Correct |
199 ms |
52836 KB |
Output is correct |
46 |
Correct |
251 ms |
52900 KB |
Output is correct |
47 |
Correct |
499 ms |
53476 KB |
Output is correct |
48 |
Correct |
6 ms |
760 KB |
Output is correct |
49 |
Correct |
30 ms |
760 KB |
Output is correct |
50 |
Correct |
134 ms |
1000 KB |
Output is correct |
51 |
Correct |
263 ms |
1400 KB |
Output is correct |
52 |
Correct |
29 ms |
4728 KB |
Output is correct |
53 |
Correct |
67 ms |
4856 KB |
Output is correct |
54 |
Correct |
258 ms |
4984 KB |
Output is correct |
55 |
Correct |
507 ms |
5584 KB |
Output is correct |
56 |
Correct |
110 ms |
21680 KB |
Output is correct |
57 |
Correct |
163 ms |
21752 KB |
Output is correct |
58 |
Correct |
422 ms |
22280 KB |
Output is correct |
59 |
Correct |
731 ms |
22448 KB |
Output is correct |
60 |
Correct |
213 ms |
43112 KB |
Output is correct |
61 |
Correct |
298 ms |
43180 KB |
Output is correct |
62 |
Correct |
609 ms |
43684 KB |
Output is correct |
63 |
Correct |
1024 ms |
44132 KB |
Output is correct |
64 |
Correct |
1354 ms |
43816 KB |
Output is correct |
65 |
Correct |
916 ms |
42744 KB |
Output is correct |
66 |
Correct |
948 ms |
42524 KB |
Output is correct |
67 |
Correct |
1077 ms |
42640 KB |
Output is correct |
68 |
Correct |
958 ms |
42864 KB |
Output is correct |
69 |
Correct |
937 ms |
43944 KB |
Output is correct |
70 |
Correct |
866 ms |
48612 KB |
Output is correct |
71 |
Correct |
742 ms |
46332 KB |
Output is correct |
72 |
Correct |
716 ms |
46084 KB |
Output is correct |
73 |
Correct |
720 ms |
46508 KB |
Output is correct |
74 |
Correct |
697 ms |
46348 KB |
Output is correct |
75 |
Correct |
739 ms |
46988 KB |
Output is correct |
76 |
Correct |
594 ms |
51708 KB |
Output is correct |
77 |
Correct |
575 ms |
49592 KB |
Output is correct |
78 |
Correct |
650 ms |
49552 KB |
Output is correct |
79 |
Correct |
546 ms |
49592 KB |
Output is correct |
80 |
Correct |
544 ms |
49596 KB |
Output is correct |
81 |
Correct |
525 ms |
50004 KB |
Output is correct |
82 |
Correct |
496 ms |
51924 KB |
Output is correct |
83 |
Correct |
509 ms |
49472 KB |
Output is correct |
84 |
Correct |
512 ms |
49608 KB |
Output is correct |
85 |
Correct |
537 ms |
49524 KB |
Output is correct |
86 |
Correct |
536 ms |
49728 KB |
Output is correct |
87 |
Correct |
552 ms |
50092 KB |
Output is correct |
88 |
Correct |
513 ms |
51816 KB |
Output is correct |
89 |
Correct |
846 ms |
42484 KB |
Output is correct |
90 |
Correct |
848 ms |
42784 KB |
Output is correct |
91 |
Correct |
743 ms |
45176 KB |
Output is correct |
92 |
Correct |
717 ms |
43560 KB |
Output is correct |
93 |
Correct |
601 ms |
48884 KB |
Output is correct |
94 |
Correct |
627 ms |
43732 KB |
Output is correct |
95 |
Correct |
564 ms |
45712 KB |
Output is correct |
96 |
Correct |
546 ms |
42400 KB |
Output is correct |
97 |
Correct |
551 ms |
45552 KB |
Output is correct |
98 |
Correct |
526 ms |
49116 KB |
Output is correct |
99 |
Correct |
616 ms |
44020 KB |
Output is correct |
100 |
Correct |
556 ms |
44020 KB |
Output is correct |