// File diameter.cpp created on 06.10.2025 at 09:23:46
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
int N, Q;
i64 W;
std::vector<i64> C;
std::vector<std::array<int, 2>> E;
std::vector<std::vector<int>> adj;
std::vector<int> par, epar;
std::vector<std::multiset<i64>> vals;
std::multiset<i64> overall;
i64 get_max(std::multiset<i64>& mset) {
if (mset.empty()) {
return 0;
}
return *mset.rbegin();
}
i64 cost(std::multiset<i64>& mset) {
if (mset.empty()) {
return 0;
}
if (mset.size() == 1) {
return *mset.rbegin();
}
return *mset.rbegin() + *++mset.rbegin();
}
void dfs(int v) {
vals[v].emplace(0);
for (auto i : adj[v]) {
int u = E[i][0] ^ E[i][1] ^ v;
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), i));
par[u] = v;
epar[u] = i;
dfs(u);
vals[v].emplace(get_max(vals[u]) + C[i]);
}
overall.emplace(cost(vals[v]));
}
void del(int v) {
std::vector<int> p {v};
while (v != 0) {
v = par[v];
p.emplace_back(v);
}
std::reverse(p.begin(), p.end());
for (int i = 0; i < int(p.size()); ++i) {
int v = p[i];
overall.extract(cost(vals[v]));
if (i + 1 == int(p.size())) {
vals[v].extract(0);
} else {
int u = p[i + 1];
vals[v].extract(get_max(vals[u]) + C[epar[u]]);
}
}
}
void add(int v) {
std::vector<int> p {v};
while (v != 0) {
v = par[v];
p.emplace_back(v);
}
vals[v].emplace(0);
for (int i = 0; i < int(p.size()); ++i) {
int v = p[i];
overall.emplace(cost(vals[v]));
if (i + 1 != int(p.size())) {
int u = p[i + 1];
vals[u].emplace(get_max(vals[v]) + C[epar[v]]);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N >> Q >> W;
adj.resize(N);
par.resize(N, -1);
epar.resize(N, -1);
E.resize(N - 1);
C.resize(N - 1);
vals.resize(N);
for (int i = 0; i < N - 1; ++i) {
std::cin >> E[i][0] >> E[i][1] >> C[i];
--E[i][0], --E[i][1];
adj[E[i][0]].emplace_back(i);
adj[E[i][1]].emplace_back(i);
}
dfs(0);
i64 last = 0;
while (Q--) {
int I;
i64 X;
std::cin >> I >> X;
I = (I + last) % (N - 1);
X = (X + last) % W;
auto[u, v] = E[I];
if (par[u] == v) {
std::swap(u, v);
}
del(v);
C[I] = X;
add(v);
last = get_max(overall);
std::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... |