#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
struct LazySegmentTree
{
int n;
vector<long long> seg;
vector<long long> lazy;
void push(int v)
{
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
seg[v * 2] += lazy[v];
seg[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
LazySegmentTree(int _n)
{
n = _n;
seg.assign(n * 4, 0);
lazy.assign(n * 4, 0);
}
void update(int l, int r, long long val, int tl, int tr, int v)
{
if (r < tl or tr < l)
return;
if (l <= tl and tr <= r)
{
seg[v] += val;
lazy[v] += val;
return;
}
push(v);
int md = (tl + tr) / 2;
update(l, r, val, tl, md, v * 2);
update(l, r, val, md + 1, tr, v * 2 + 1);
seg[v] = max(seg[v * 2], seg[v * 2 + 1]);
}
void update(int l, int r, long long val)
{
update(l, r, val, 0, n - 1, 1);
}
long long query(int l, int r, int tl, int tr, int v)
{
if (r < tl or tr < l)
return 0;
if (l <= tl and tr <= r)
return seg[v];
push(v);
int md = (tl + tr) / 2;
return max(query(l, r, tl, md, v * 2), query(l, r, md + 1, tr, v * 2 + 1));
}
long long query(int l, int r)
{
return query(l, r, 0, n - 1, 1);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
long long w;
cin >> n >> q >> w;
vector<tuple<int, int, long long>> edges(n);
for (int i = 1; i < n; i++)
{
auto &[u, v, c] = edges[i];
cin >> u >> v >> c;
if (u > v)
swap(u, v);
}
vector adj(n + 1, vector<pair<int, long long>>());
for (int i = 1; i < n; i++)
{
auto [u, v, c] = edges[i];
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
vector<int> in(n + 1), out(n + 1), par(n + 1), euler(n);
vector<long long> sum(n + 1);
LazySegmentTree seg(n);
int timer = 0;
auto dfs = [&](auto self, int u, int p, int pp) -> void
{
par[u] = pp;
euler[timer] = u;
in[u] = timer++;
for (auto [v, c] : adj[u])
{
if (v == p)
continue;
bool can = pp == -1;
if (can)
pp = v;
self(self, v, u, pp);
if (can)
pp = -1;
}
out[u] = timer;
};
dfs(dfs, 1, -1, -1);
for (int i = 1; i < n; i++)
{
auto &[u, v, c] = edges[i];
if (in[u] > in[v])
swap(u, v);
seg.update(in[v], out[v] - 1, c);
}
multiset<long long> st;
st.insert(0);
for (auto [v, c] : adj[1])
{
st.insert(seg.query(in[v], out[v] - 1));
}
long long lst = 0;
while (q--)
{
int d;
long long e;
cin >> d >> e;
d = (d + lst) % (n - 1) + 1;
e = (e + lst) % w;
auto &[u, vv, c] = edges[d];
long long bef = c;
c = e;
st.erase(st.find(seg.query(in[par[vv]], out[par[vv]] - 1)));
// for(auto [v, c]: adj[1])
// {
// cout << v << ' ' << seg.query(in[v], out[v] - 1) << '\n';
// }
// cout << "\n\n";
seg.update(in[vv], out[vv] - 1, c - bef);
// for(auto [v, c]: adj[1])
// {
// cout << v << ' ' << seg.query(in[v], out[v] - 1) << '\n';
// }
st.insert(seg.query(in[par[vv]], out[par[vv]] - 1));
long long res = *prev(st.end()) + *prev(prev(st.end()));
cout << res << '\n';
lst = res;
}
}
# | 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... |