// subtask4
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 1;
vector <vector <pair <int, ll>>> adj;
struct edge {
int a, b;
ll w;
};
vector<edge> edges;
vector <int> st_sz, id;
vector <ll> path_len(MAX_N);
vector <int> euler;
int dfs(int s, int p) {
euler.push_back(s);
int visited = 1;
for (auto i : adj[s]) {
if (i.first == p)
continue;
path_len[i.first] = path_len[s] + i.second;
visited += dfs(i.first, s);
}
st_sz[s] = visited;
return visited;
}
struct sgtree_node {
ll val, lazy_val;
bool updates_pending;
};
struct seg_tree {
#define lc v*2
#define rc v*2+1
vector <sgtree_node> tree;
int sz;
seg_tree (int size) {
sz = size;
tree = vector <sgtree_node> (4 * size);
};
ll combine(ll lval, ll rval) {
return max(lval, rval);
}
void pushup(int v) {
tree[v].val = combine(tree[lc].val, tree[rc].val);
}
void pushdown(int v) {
if (!tree[v].updates_pending)
return;
tree[lc].val += tree[v].lazy_val;
tree[rc].val += tree[v].lazy_val;
tree[lc].lazy_val += tree[v].lazy_val;
tree[rc].lazy_val += tree[v].lazy_val;
tree[v].lazy_val = 0;
tree[v].updates_pending = false;
tree[lc].updates_pending = tree[rc].updates_pending = false;
}
void build(int v, int tl, int tr, int l, int r, vector <ll> &arr) {
if (tl == tr) {
tree[v].val += arr[tl];
return;
}
pushdown(v);
int tm = (tl + tr) / 2;
build(lc, tl, tm, l, r, arr);
build(rc, tm+1, tr, l, r, arr);
pushup(v);
}
void update(int v, int tl, int tr, int l, int r, ll lazy_val) {
if (l > tr || r < tl)
return;
if (tl >= l && tr <= r) {
tree[v].val += lazy_val;
tree[v].updates_pending = true;
tree[v].lazy_val += lazy_val;
return;
}
pushdown(v);
int tm = (tl + tr) / 2;
update(lc, lc, tm, l, r, lazy_val);
update(rc, tm+1, tr, l, r, lazy_val);
pushup(v);
}
ll query(int v, int tl, int tr, int l, int r) {
if (l > tr || r < tl)
return 0;
if (tl >= l && tr <= r)
return tree[v].val;
pushdown(v);
int tm = (tl + tr) / 2;
return combine(query(lc, tl, tm, l, r), query(rc, tm+1, tr, l, r));
}
};
int main() {
int N, Q;
ll W;
cin >> N >> Q >> W;
// initialise stuff
adj = vector <vector <pair <int, ll>>> (N+1);
edges = vector <edge> (N);
st_sz = vector <int> (N+1);
id = vector <int> (N+1);
for (int i = 0; i < N-1; i++) {
int a, b;
ll w;
cin >> a >> b >> w;
edge tp;
tp.a = a;
tp.b = b;
tp.w = w;
edges[i] = tp;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
euler.push_back(0);
dfs(1, 1);
for (int i = 1; i <= N; i++)
id[euler[i]] = i;
seg_tree tree(N+1);
tree.build(1, 1, N, 1, st_sz[1], path_len);
multiset <ll> lens;
for (auto i : adj[1]) {
ll x = tree.query(1, 1, N, i.first, i.first + st_sz[i.first] - 1);
cout << x << '\n';
lens.insert(x);
}
ll last = 0;
while (Q--) {
ll d, e;
cin >> d >> e;
d = (d + last) % (N-1);
e = (e + last) % (W);
int a = edges[d].a, b = edges[d].b;
if (path_len[a] > path_len[b])
swap(a, b);
ll w = edges[d].w;
ll delta = e - w;
edges[d].w = e;
ll og_len = tree.query(1, 1, N, id[b], id[b] + st_sz[id[b]] - 1);
if (lens.find(og_len) != lens.end())
lens.erase(lens.find(og_len));
// tree.update(1, 1, N, id[b], id[b] + st_sz[b] - 1, delta);
ll new_len = tree.query(1, 1, N, id[b], id[b] + st_sz[id[b]] - 1);
lens.insert(new_len);
if (!lens.empty())
last = *lens.rbegin();
if (lens.size() >= 2)
last += *(--(--lens.end()));
cout << last << '\n';
}
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:157:12: warning: unused variable 'delta' [-Wunused-variable]
157 | ll delta = e - w;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
525 ms |
24400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
