#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define sz(x) (int)x.size()
#define f first
#define s second
/*
Date: 2022/07/12 19:14
Problem Link: https://dmoj.ca/problem/ceoi19p2/
Topic(s): Segment tree, Euler tour
Time Spent:
Solution Notes:
By creating a segment tree, each node holds 4 values:
1. d_i = distance to the root
2. max(d_l - 2*d_m)
3. max(d_r - 2*d_m)
4. max(d_l + d_r - 2*d_m)
*/
const int MAXN = 1e5+5;
const ll INF = 5e17;
int n, q, in[MAXN], out[MAXN], dep[MAXN], timer = 0;
ll dp[MAXN];
vector<pair<int, ll>> arr[MAXN];
vector<int> tour;
ll w;
void dfs(int at, int p, int d, ll dist){
tour.push_back(at);
in[at] = timer++;
dep[at] = d;
dp[at] = dist;
for (auto edge : arr[at]){
if (edge.f != p){
dfs(edge.f, at, d+1, dist + edge.s);
tour.push_back(at);
timer++;
}
}
tour.push_back(at);
out[at] = timer++;
}
struct Node{
ll di_max, di_min, pre, suf, ans;
};
struct segtree{
int n;
Node identity = {0, INF, -INF, -INF, 0};
vector<Node> seg;
vector<ll> lazy;
vector<ll> arr;
segtree(int n){
this->n = n;
seg.resize(4*n, identity);
lazy.resize(4*n);
}
void build(vector<ll>& arr){
this->arr = arr;
build(0, 0, n-1);
}
void build(int node, int l, int r){
if (l == r) {
seg[node] = {arr[l], arr[l], -arr[l], -arr[l], 0};
return;
}
int mid = (l + r) / 2;
build(node * 2 + 1, l, mid);
build(node * 2 + 2, mid + 1, r);
// change this
seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
}
ll query(){
return seg[0].ans;
}
void update(int a, int b, ll x) { // inclusive 0-indexed
update(0, 0, n-1, a, b, x);
}
void update(int node, int l, int r, int a, int b, ll x) {
int numElements = r - l + 1;
if (a <= l && r <= b) {
apply(node, l, r, x);
return;
}
prop(node, l, r);
int mid = (l + r) / 2;
if (a <= mid) {
update(node * 2 + 1, l, mid, a, b, x);
}
if (b > mid) {
update(node * 2 + 2, mid + 1, r, a, b, x);
}
// change this
seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
}
void prop(int node, int l, int r) { // propagate the "lazy value"
if (lazy[node] != 0) {
int mid = (l + r) / 2;
// change this
apply(node*2+1, l, mid, lazy[node]);
apply(node*2+2, mid+1, r, lazy[node]);
lazy[node] = 0;
}
}
void apply(ll node, ll l, ll r, ll x){
seg[node].di_min += x;
seg[node].di_max += x;
seg[node].pre -= x;
seg[node].suf -= x;
lazy[node] += x;
}
Node combine(Node a, Node b){
ll di_min = min(a.di_min, b.di_min);
ll di_max = max(a.di_max, b.di_max);
ll pre = max({a.pre, b.pre, a.di_max - 2*b.di_min});
ll suf = max({a.suf, b.suf, b.di_max - 2*a.di_min});
ll ans = max({a.ans, b.ans, a.pre + b.di_max, b.suf + a.di_max});
return {di_max, di_min, pre, suf, ans};
}
};
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> q >> w;
vector<array<ll, 3>> edges(n-1);
for (int i=0; i<n-1; i++){
int a, b;
ll c;
cin >> a >> b >> c;
a--; b--;
edges[i] = {a, b, c};
arr[a].push_back({b, c});
arr[b].push_back({a, c});
}
dfs(0, -1, 0, 0);
vector<ll> segtreeInit;
for (int i=0; i<sz(tour); i++){
segtreeInit.push_back(dp[tour[i]]);
}
segtree st(sz(tour));
st.build(segtreeInit);
ll last = 0;
for (int i=0; i<q; i++){
int a;
ll b;
cin >> a >> b;
a = (a + last)%(n-1);
b = (b + last)%w;
int subtree = dep[edges[a][0]] > dep[edges[a][1]] ? edges[a][0] : edges[a][1];
st.update(in[subtree], out[subtree], b - edges[a][2]);
edges[a][2] = b;
last = st.query();
cout << last << "\n";
}
}
Compilation message
diameter.cpp: In member function 'void segtree::update(int, int, int, int, int, ll)':
diameter.cpp:85:7: warning: unused variable 'numElements' [-Wunused-variable]
85 | int numElements = r - l + 1;
| ^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2680 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2680 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2676 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2676 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2680 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2684 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2680 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2680 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2676 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2676 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2680 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2684 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
6 ms |
3540 KB |
Output is correct |
20 |
Correct |
5 ms |
3456 KB |
Output is correct |
21 |
Correct |
7 ms |
3436 KB |
Output is correct |
22 |
Correct |
6 ms |
3540 KB |
Output is correct |
23 |
Correct |
9 ms |
6548 KB |
Output is correct |
24 |
Correct |
8 ms |
6484 KB |
Output is correct |
25 |
Correct |
9 ms |
6524 KB |
Output is correct |
26 |
Correct |
9 ms |
6868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
8 ms |
2900 KB |
Output is correct |
5 |
Correct |
32 ms |
3848 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
3028 KB |
Output is correct |
8 |
Correct |
2 ms |
3028 KB |
Output is correct |
9 |
Correct |
3 ms |
3076 KB |
Output is correct |
10 |
Correct |
10 ms |
3320 KB |
Output is correct |
11 |
Correct |
41 ms |
4300 KB |
Output is correct |
12 |
Correct |
5 ms |
6356 KB |
Output is correct |
13 |
Correct |
5 ms |
6356 KB |
Output is correct |
14 |
Correct |
6 ms |
6484 KB |
Output is correct |
15 |
Correct |
14 ms |
6696 KB |
Output is correct |
16 |
Correct |
54 ms |
7844 KB |
Output is correct |
17 |
Correct |
64 ms |
75176 KB |
Output is correct |
18 |
Correct |
63 ms |
75148 KB |
Output is correct |
19 |
Correct |
66 ms |
75352 KB |
Output is correct |
20 |
Correct |
86 ms |
75512 KB |
Output is correct |
21 |
Correct |
167 ms |
76880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
9 ms |
3592 KB |
Output is correct |
3 |
Correct |
29 ms |
4040 KB |
Output is correct |
4 |
Correct |
55 ms |
4732 KB |
Output is correct |
5 |
Correct |
11 ms |
10108 KB |
Output is correct |
6 |
Correct |
16 ms |
10320 KB |
Output is correct |
7 |
Correct |
42 ms |
10832 KB |
Output is correct |
8 |
Correct |
75 ms |
11652 KB |
Output is correct |
9 |
Correct |
37 ms |
39612 KB |
Output is correct |
10 |
Correct |
45 ms |
39664 KB |
Output is correct |
11 |
Correct |
87 ms |
40380 KB |
Output is correct |
12 |
Correct |
129 ms |
41144 KB |
Output is correct |
13 |
Correct |
71 ms |
76416 KB |
Output is correct |
14 |
Correct |
81 ms |
76452 KB |
Output is correct |
15 |
Correct |
122 ms |
77196 KB |
Output is correct |
16 |
Correct |
173 ms |
78212 KB |
Output is correct |
17 |
Correct |
191 ms |
77796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
233 ms |
80128 KB |
Output is correct |
2 |
Correct |
233 ms |
80156 KB |
Output is correct |
3 |
Correct |
230 ms |
80152 KB |
Output is correct |
4 |
Correct |
231 ms |
80180 KB |
Output is correct |
5 |
Correct |
215 ms |
80084 KB |
Output is correct |
6 |
Correct |
203 ms |
79960 KB |
Output is correct |
7 |
Correct |
248 ms |
82616 KB |
Output is correct |
8 |
Correct |
250 ms |
82664 KB |
Output is correct |
9 |
Correct |
239 ms |
82564 KB |
Output is correct |
10 |
Correct |
238 ms |
82604 KB |
Output is correct |
11 |
Correct |
238 ms |
82416 KB |
Output is correct |
12 |
Correct |
223 ms |
81616 KB |
Output is correct |
13 |
Correct |
267 ms |
86328 KB |
Output is correct |
14 |
Correct |
278 ms |
86424 KB |
Output is correct |
15 |
Correct |
272 ms |
86332 KB |
Output is correct |
16 |
Correct |
269 ms |
86468 KB |
Output is correct |
17 |
Correct |
306 ms |
85792 KB |
Output is correct |
18 |
Correct |
251 ms |
82936 KB |
Output is correct |
19 |
Correct |
278 ms |
86348 KB |
Output is correct |
20 |
Correct |
303 ms |
86368 KB |
Output is correct |
21 |
Correct |
357 ms |
86476 KB |
Output is correct |
22 |
Correct |
299 ms |
86324 KB |
Output is correct |
23 |
Correct |
316 ms |
85736 KB |
Output is correct |
24 |
Correct |
255 ms |
82992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2680 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2680 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2676 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2676 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2680 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2684 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
6 ms |
3540 KB |
Output is correct |
20 |
Correct |
5 ms |
3456 KB |
Output is correct |
21 |
Correct |
7 ms |
3436 KB |
Output is correct |
22 |
Correct |
6 ms |
3540 KB |
Output is correct |
23 |
Correct |
9 ms |
6548 KB |
Output is correct |
24 |
Correct |
8 ms |
6484 KB |
Output is correct |
25 |
Correct |
9 ms |
6524 KB |
Output is correct |
26 |
Correct |
9 ms |
6868 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
8 ms |
2900 KB |
Output is correct |
31 |
Correct |
32 ms |
3848 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
3028 KB |
Output is correct |
34 |
Correct |
2 ms |
3028 KB |
Output is correct |
35 |
Correct |
3 ms |
3076 KB |
Output is correct |
36 |
Correct |
10 ms |
3320 KB |
Output is correct |
37 |
Correct |
41 ms |
4300 KB |
Output is correct |
38 |
Correct |
5 ms |
6356 KB |
Output is correct |
39 |
Correct |
5 ms |
6356 KB |
Output is correct |
40 |
Correct |
6 ms |
6484 KB |
Output is correct |
41 |
Correct |
14 ms |
6696 KB |
Output is correct |
42 |
Correct |
54 ms |
7844 KB |
Output is correct |
43 |
Correct |
64 ms |
75176 KB |
Output is correct |
44 |
Correct |
63 ms |
75148 KB |
Output is correct |
45 |
Correct |
66 ms |
75352 KB |
Output is correct |
46 |
Correct |
86 ms |
75512 KB |
Output is correct |
47 |
Correct |
167 ms |
76880 KB |
Output is correct |
48 |
Correct |
3 ms |
3412 KB |
Output is correct |
49 |
Correct |
9 ms |
3592 KB |
Output is correct |
50 |
Correct |
29 ms |
4040 KB |
Output is correct |
51 |
Correct |
55 ms |
4732 KB |
Output is correct |
52 |
Correct |
11 ms |
10108 KB |
Output is correct |
53 |
Correct |
16 ms |
10320 KB |
Output is correct |
54 |
Correct |
42 ms |
10832 KB |
Output is correct |
55 |
Correct |
75 ms |
11652 KB |
Output is correct |
56 |
Correct |
37 ms |
39612 KB |
Output is correct |
57 |
Correct |
45 ms |
39664 KB |
Output is correct |
58 |
Correct |
87 ms |
40380 KB |
Output is correct |
59 |
Correct |
129 ms |
41144 KB |
Output is correct |
60 |
Correct |
71 ms |
76416 KB |
Output is correct |
61 |
Correct |
81 ms |
76452 KB |
Output is correct |
62 |
Correct |
122 ms |
77196 KB |
Output is correct |
63 |
Correct |
173 ms |
78212 KB |
Output is correct |
64 |
Correct |
191 ms |
77796 KB |
Output is correct |
65 |
Correct |
233 ms |
80128 KB |
Output is correct |
66 |
Correct |
233 ms |
80156 KB |
Output is correct |
67 |
Correct |
230 ms |
80152 KB |
Output is correct |
68 |
Correct |
231 ms |
80180 KB |
Output is correct |
69 |
Correct |
215 ms |
80084 KB |
Output is correct |
70 |
Correct |
203 ms |
79960 KB |
Output is correct |
71 |
Correct |
248 ms |
82616 KB |
Output is correct |
72 |
Correct |
250 ms |
82664 KB |
Output is correct |
73 |
Correct |
239 ms |
82564 KB |
Output is correct |
74 |
Correct |
238 ms |
82604 KB |
Output is correct |
75 |
Correct |
238 ms |
82416 KB |
Output is correct |
76 |
Correct |
223 ms |
81616 KB |
Output is correct |
77 |
Correct |
267 ms |
86328 KB |
Output is correct |
78 |
Correct |
278 ms |
86424 KB |
Output is correct |
79 |
Correct |
272 ms |
86332 KB |
Output is correct |
80 |
Correct |
269 ms |
86468 KB |
Output is correct |
81 |
Correct |
306 ms |
85792 KB |
Output is correct |
82 |
Correct |
251 ms |
82936 KB |
Output is correct |
83 |
Correct |
278 ms |
86348 KB |
Output is correct |
84 |
Correct |
303 ms |
86368 KB |
Output is correct |
85 |
Correct |
357 ms |
86476 KB |
Output is correct |
86 |
Correct |
299 ms |
86324 KB |
Output is correct |
87 |
Correct |
316 ms |
85736 KB |
Output is correct |
88 |
Correct |
255 ms |
82992 KB |
Output is correct |
89 |
Correct |
224 ms |
79188 KB |
Output is correct |
90 |
Correct |
236 ms |
79532 KB |
Output is correct |
91 |
Correct |
243 ms |
80896 KB |
Output is correct |
92 |
Correct |
243 ms |
80820 KB |
Output is correct |
93 |
Correct |
256 ms |
83192 KB |
Output is correct |
94 |
Correct |
266 ms |
82364 KB |
Output is correct |
95 |
Correct |
269 ms |
83800 KB |
Output is correct |
96 |
Correct |
291 ms |
82904 KB |
Output is correct |
97 |
Correct |
265 ms |
83720 KB |
Output is correct |
98 |
Correct |
293 ms |
85688 KB |
Output is correct |
99 |
Correct |
267 ms |
83468 KB |
Output is correct |
100 |
Correct |
266 ms |
83516 KB |
Output is correct |