#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 9;
struct node {
long long a = 0, b = 0, c = 0, d = 0, e = 0;
node operator+(const node &oth) const {
node ret;
ret.a = max(a, oth.a);
ret.b = max(b, oth.b);
ret.c = max(max(c, oth.c), a + oth.b);
ret.d = max(max(d, oth.d), b + oth.a);
ret.e = max(max(e, oth.e), max(c + oth.a, a + oth.d));
return ret;
}
};
struct ST {
#define lc (n << 1)
#define rc ((n << 1) | 1)
long long lazy[4 * N * 2];
node t[4 * N * 2];
ST() {
fill(lazy, lazy + 4 * N * 2, 0);
}
inline void push(int n, int b, int e) {
if (lazy[n] == 0) return;
long long v = lazy[n];
t[n].a += v;
t[n].b -= 2 * v;
t[n].c -= v;
t[n].d -= v;
if (b != e) {
lazy[lc] += v;
lazy[rc] += v;
}
lazy[n] = 0;
}
inline void pull(int n) {
t[n] = t[lc] + t[rc];
}
void build(int n, int b, int e, const vector<long long>& dist, const vector<int>& q) {
if (b == e) {
t[n].a = dist[q[b]];
t[n].b = -2 * dist[q[b]];
t[n].c = -dist[q[b]];
t[n].d = -dist[q[b]];
t[n].e = 0;
return;
}
int mid = (b + e) >> 1;
build(lc, b, mid, dist, q);
build(rc, mid + 1, e, dist, q);
pull(n);
}
void upd(int n, int b, int e, int i, int j, long long v) {
push(n, b, e);
if (j < b || e < i) return;
if (i <= b && e <= j) {
lazy[n] += v;
push(n, b, e);
return;
}
int mid = (b + e) >> 1;
upd(lc, b, mid, i, j, v);
upd(rc, mid + 1, e, i, j, v);
pull(n);
}
} t;
long long W[N];
vector<pair<int, int>> g[N];
int T, st[N * 2], en[N * 2], pos[N];
vector<long long> dist;
vector<int> q_nodes;
void dfs(int u, int p = 0, long long current_dist = 0) {
st[u] = ++T;
q_nodes[T] = u;
dist[u] = current_dist;
for (auto e : g[u]) {
int v = e.first, i = e.second;
if (v == p) continue;
pos[i] = v;
dfs(v, u, current_dist + W[i]);
q_nodes[++T] = u;
}
en[u] = T;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
long long mod;
cin >> n >> q >> mod;
dist.resize(n + 1);
q_nodes.resize(2 * n);
for (int i = 1; i < n; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
g[u].push_back({v, i});
g[v].push_back({u, i});
W[i] = w;
}
T = 0;
dfs(1);
t.build(1, 1, T, dist, q_nodes);
long long last = 0;
while (q--) {
int d;
long long e;
cin >> d >> e;
d = (d + last) % (n - 1) + 1;
e = (e + last) % mod;
t.upd(1, 1, T, st[pos[d]], en[pos[d]], e - W[d]);
W[d] = e;
last = t.t[1].e;
cout << last << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |