#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
#define int ll
struct node {
int val, lazy;
};
struct update {
int x, l, r, ql, qr, id, cent, edgeid;
};
struct edge {
int to; ll cost; int id;
};
vector<update> history[100005];
vector<edge> adj[100005];
int sz[100005];
bool seen[100005];
int timer = 1;
int st[100005], en[100005];
multiset<ll> pathd[100005], total;
int ct = 0;
vector<vector<node>> tree;
ll get() {
return *prev(total.end());
}
ll calc(multiset<ll> &cur) {
if (cur.empty()) return 0;
if (cur.size() == 1) return *cur.begin();
auto itr = cur.end(); itr--;
ll sum = *itr; itr--;
sum += *itr;
return sum;
}
void predfs(int node, int par = -1) {
ct++;
sz[node] = 1;
for (auto nxt : adj[node]) {
if (nxt.to == par)continue;
if (seen[nxt.to]) continue;
predfs(nxt.to, node);
sz[node] += sz[nxt.to];
}
}
int find(int node, int root, int par = -1) {
for (auto nxt : adj[node]) {
if (seen[nxt.to]) continue;
if (nxt.to == par)continue;
if (sz[nxt.to] * 2 > sz[root]) return find(nxt.to, root, node);
}
return node;
}
void dfs(int node, int par = -1) {
st[node] = timer++;
for (auto nxt : adj[node]) {
if (seen[nxt.to] || nxt.to == par) continue;
dfs(nxt.to, node);
}
en[node] = timer - 1;
}
void pushdown(int x, int l, int r, int id) {
if (l == r) return;
tree[id][2 * x].val += tree[id][x].lazy;
tree[id][2 * x].lazy += tree[id][x].lazy;
tree[id][2 * x + 1].val += tree[id][x].lazy;
tree[id][2 * x + 1].lazy += tree[id][x].lazy;
tree[id][x].lazy = 0;
}
void update(int x, int l, int r, int ql, int qr, int id, int cent, int v) {
if (ql <= l && r <= qr) {
if (x == 1) {
pathd[cent].erase(pathd[cent].find(tree[id][x].val));
}
tree[id][x].val += v;
tree[id][x].lazy += v;
if (x == 1) {
pathd[cent].insert(tree[id][x].val);
}
return;
}
if (l > qr || ql > r) return;
pushdown(x, l, r, id);
int mid = (l + r) / 2;
update(2 * x, l, mid, ql, qr, id, cent, v);
update(2 * x + 1, mid + 1, r, ql, qr, id, cent, v);
if (x == 1) {
pathd[cent].erase(pathd[cent].find(tree[id][x].val));
}
tree[id][x].val = max(tree[id][2 * x].val, tree[id][2 * x + 1].val);
if (x == 1) {
pathd[cent].insert(tree[id][x].val);
}
}
void updateall(int node, int par, int cent) {
for (auto nxt : adj[node]) {
if (seen[nxt.to] || par == nxt.to) continue;
update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});
updateall(nxt.to, node, cent);
}
}
void centroid(int node) {
ct = 0;
predfs(node);
if (ct == 1) {
seen[node] = true; return;
}
int cent = find(node, node);
for (auto nxt : adj[cent]) {
if (seen[nxt.to]) continue;
timer = 1;
dfs(nxt.to, cent);
tree.push_back({});
tree.back().resize(4 * (timer + 1));
pathd[cent].insert(0);
update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});
updateall(nxt.to, cent, cent);
}
total.insert(calc(pathd[cent]));
seen[cent] = true;
for (auto nxt : adj[node]) {
if (seen[nxt.to]) continue;
centroid(nxt.to);
}
}
ll edgeinfo[100005];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n, q, w; cin >> n >> q >> w;
for (int i = 1; i <= n-1; i++) {
int a, b; cin >> a >> b;
ll c; cin >> c;
adj[a].push_back({b, c, i});
adj[b].push_back({a, c, i});
edgeinfo[i] = c;
}
centroid(1);
// cout << *prev(total.end()) << endl;
ll last = 0;
for (int i = 0; i < q; i++) {
ll d, e; cin >> d >> e;
d = (d + last) % (n - 1);
d++;
e = (e + last) % w;
ll delta = e - edgeinfo[d];
edgeinfo[d] = e;
for (auto [x, l, r, ql, qr, id, cent, edgeid] : history[d]) {
total.erase(total.find(calc(pathd[cent])));
update(x, l, r, ql, qr, id, cent, delta);
total.insert(calc(pathd[cent]));
}
last = get();
cout << last << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9800 KB |
Output is correct |
2 |
Correct |
5 ms |
9728 KB |
Output is correct |
3 |
Correct |
6 ms |
9740 KB |
Output is correct |
4 |
Correct |
14 ms |
9872 KB |
Output is correct |
5 |
Correct |
47 ms |
10880 KB |
Output is correct |
6 |
Correct |
6 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9940 KB |
Output is correct |
8 |
Correct |
6 ms |
9860 KB |
Output is correct |
9 |
Correct |
7 ms |
9988 KB |
Output is correct |
10 |
Correct |
16 ms |
10176 KB |
Output is correct |
11 |
Correct |
52 ms |
11224 KB |
Output is correct |
12 |
Correct |
9 ms |
11980 KB |
Output is correct |
13 |
Correct |
10 ms |
11916 KB |
Output is correct |
14 |
Correct |
11 ms |
12044 KB |
Output is correct |
15 |
Correct |
23 ms |
12264 KB |
Output is correct |
16 |
Correct |
67 ms |
13392 KB |
Output is correct |
17 |
Correct |
146 ms |
54776 KB |
Output is correct |
18 |
Correct |
179 ms |
54804 KB |
Output is correct |
19 |
Correct |
153 ms |
55020 KB |
Output is correct |
20 |
Correct |
179 ms |
55116 KB |
Output is correct |
21 |
Correct |
377 ms |
56400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
10132 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
403 ms |
48516 KB |
Output is correct |
2 |
Correct |
375 ms |
49076 KB |
Output is correct |
3 |
Correct |
332 ms |
44996 KB |
Output is correct |
4 |
Correct |
456 ms |
52948 KB |
Output is correct |
5 |
Correct |
337 ms |
47200 KB |
Output is correct |
6 |
Correct |
467 ms |
63472 KB |
Output is correct |
7 |
Correct |
524 ms |
58508 KB |
Output is correct |
8 |
Correct |
541 ms |
58532 KB |
Output is correct |
9 |
Correct |
517 ms |
58388 KB |
Output is correct |
10 |
Correct |
504 ms |
58496 KB |
Output is correct |
11 |
Correct |
465 ms |
57988 KB |
Output is correct |
12 |
Correct |
602 ms |
68332 KB |
Output is correct |
13 |
Correct |
568 ms |
61384 KB |
Output is correct |
14 |
Correct |
542 ms |
61596 KB |
Output is correct |
15 |
Correct |
571 ms |
61440 KB |
Output is correct |
16 |
Correct |
612 ms |
61772 KB |
Output is correct |
17 |
Correct |
482 ms |
62100 KB |
Output is correct |
18 |
Correct |
645 ms |
71580 KB |
Output is correct |
19 |
Correct |
608 ms |
61320 KB |
Output is correct |
20 |
Correct |
608 ms |
61540 KB |
Output is correct |
21 |
Correct |
627 ms |
61480 KB |
Output is correct |
22 |
Correct |
621 ms |
61604 KB |
Output is correct |
23 |
Correct |
572 ms |
61992 KB |
Output is correct |
24 |
Correct |
743 ms |
71680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |