#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
#define int long long
const int N = 8e5 + 10;
int out[N], in[N], d[N];
vector<int> a;
vector<pair<int, int>> adj[N];
void dfs(int u, int par) {
in[u] = out[u] = sz(a);
a.pb(u);
for(auto x: adj[u]) {
int v = x.first, w = x.second;
if(v == par) continue;
d[v] = d[u] + w;
dfs(v, u);
out[u] = sz(a);
a.pb(u);
}
}
struct node {
int prefix, sufix, ans, max_depth, max_lca;
};
node merge(node a, node b) {
node c;
c.prefix = max({a.prefix, b.prefix, b.max_depth + a.max_lca});
c.sufix = max({a.sufix, b.sufix, a.max_depth + b.max_lca});
c.max_depth = max(a.max_depth, b.max_depth);
c.max_lca = max(a.max_lca, b.max_lca);
c.ans = max({a.ans, b.ans, a.sufix + b.max_depth, a.max_depth + b.prefix});
return c;
}
node t[4 * N];
int lazy[4 * N];
void push(int i, int l, int r) {
if(!lazy[i]) return;
t[i].max_depth += lazy[i];
t[i].max_lca -= 2 * lazy[i];
t[i].prefix -= lazy[i];
t[i].sufix -= lazy[i];
if(l != r) {
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, int val) {
push(i, l, r);
if(l > tr || r < tl) return;
if(l >= tl && r <= tr) {
lazy[i] += val;
push(i, l, r);
return;
}
int mid = l + r >> 1;
modif(2 * i, l, mid, tl, tr, val);
modif(2 * i + 1, mid + 1, r, tl, tr, val);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
const int inf = 1e9;
const node neutral = {-inf, -inf, -inf, -inf, -inf};
void build(int i, int l, int r) {
if(l > r) return;
if(l == r) {
t[i].max_depth = d[a[l]];
t[i].max_lca = -2 * d[a[l]];
t[i].prefix = -2 * d[a[l]];
t[i].sufix = -2 * d[a[l]];
t[i].ans = d[a[l]];
return;
}
int mid = l + r >> 1;
build(2 * i, l, mid);
build(2 * i + 1, mid + 1, r);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
void solve() {
a.clear();
for(int i = 0; i < 4 * N; ++i) t[i] = neutral;
int n, q, w; cin >> n >> q >> w;
vector<pair<int, int>> edges;
map<pair<int, int>, int> mp;
for(int i = 0; i < n - 1; ++i) {
int u, v, c; cin >> u >> v >> c; --u, --v;
adj[u].pb({v, c});
adj[v].pb({u, c});
edges.pb({u, v});
mp[{u, v}] = mp[{v, u}] = c;
}
dfs(0, -1);
for(int i = 0; i < n - 1; ++i) {
if(in[edges[i].first] > in[edges[i].second]) swap(edges[i].first, edges[i].second);
}
build(1, 0, sz(a) - 1);
int last = 0;
while(q--) {
int d, e; cin >> d >> e; d = (d + last) % (n - 1), e = (e + last) % w;
modif(1, 0, sz(a) - 1, in[edges[d].second], out[edges[d].second], e - mp[{edges[d].first, edges[d].second}]);
last = t[1].ans;
mp[{edges[d].first, edges[d].second}] = mp[{edges[d].second, edges[d].first}] = e;
cout << last << "\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
Compilation message
diameter.cpp: In function 'void modif(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In function 'void build(long long int, long long int, long long int)':
diameter.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
144264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
144264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
144340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
144600 KB |
Output is correct |
| 2 |
Incorrect |
67 ms |
144672 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
600 ms |
173556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
144264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
