#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
int nds[N]; // map edges to node
ll a[N];
vector<int> adj[N];
vector<pair<pair<int, int>, ll>> adj2[N];
enum Type { Compress, Vertex, AddVertex, AddEdge, Rake };
struct StaticTopTree {
int l[4 * N], r[4 * N], p[4 * N], root, idx;
Type t[4 * N];
int dfs(int v) {
int sz = 1, big = 0;
for (auto& x : adj[v]) {
int s = dfs(x);
sz += s;
if (big < s) big = s, swap(x, adj[v][0]);
}
return sz;
}
int add(int v, int lc, int rc, Type type) {
if (v == -1) v = ++idx;
p[v] = -1, l[v] = lc, r[v] = rc, t[v] = type;
if (lc != -1) p[lc] = v;
if (rc != -1) p[rc] = v;
return v;
}
pair<int, int> merge(vector<pair<int, int>>& path, Type type) {
if ((int)path.size() == 1) return path[0];
int sz = 0;
for (auto& [_, s] : path) sz += s;
vector<pair<int, int>> pl, pr;
for (auto& [x, s] : path) {
(s < sz ? pl : pr).push_back({ x, s }), sz -= 2 * s;
}
auto [i, si] = merge(pl, type);
auto [j, sj] = merge(pr, type);
return { add(-1, i, j, type), si + sj };
}
pair<int, int> rake(int i) {
vector<pair<int, int>> path;
for (int j = 1;j < (int)adj[i].size();j++) {
path.push_back(add_edge(adj[i][j]));
}
return path.empty() ? make_pair(-1, 0) : merge(path, Type::Rake);
}
pair<int, int> compress(int i) {
vector<pair<int, int>> path{ add_vertex(i) };
while (!adj[i].empty()) path.push_back(add_vertex(i = adj[i][0]));
return merge(path, Type::Compress);
}
pair<int, int> add_vertex(int i) {
auto [j, s] = rake(i);
return { add(i, j, -1, j == -1 ? Type::Vertex : Type::AddVertex), s + 1 };
}
pair<int, int> add_edge(int i) {
auto [j, s] = compress(i);
return { add(-1, j, -1, Type::AddEdge), s };
}
void build() {
idx = n;
dfs(1);
root = compress(1).first;
}
} stt;
void dfsd(int v, int p = -1) {
for (auto& x : adj2[v]) {
if (x.first.second == p) continue;
nds[x.first.first] = x.first.second;
a[x.first.second] = x.second;
adj[v].push_back(x.first.second);
dfsd(x.first.second, v);
}
}
struct Point {
ll mx, mx1, mx2;
} point[4 * N];
struct Path {
ll mx, l, pref, mxp;
} path[4 * N];
Path vertex(int i) {
return { 0ll, a[i], a[i], a[i] };
}
Path add_vertex(Point d, int i) {
return { max(d.mx, d.mx1 + d.mx2), a[i], a[i] + d.mx1, d.mx1 };
}
Path compress(Path p, Path c) {
return{ max({p.mx, c.mx, p.mxp + c.pref}), p.l + c.l, max(c.pref + p.l, p.pref), max(c.mxp, p.mxp + c.l) };
}
Point add_edge(Path d) {
return { d.mx, d.pref, 0ll };
}
Point rake(Point l, Point r) {
Point res = { max(l.mx, r.mx), l.mx1, l.mx2 };
res.mx2 = max(res.mx2, r.mx1);
if (res.mx1 < res.mx2) swap(res.mx1, res.mx2);
res.mx2 = max(res.mx2, r.mx2);
if (res.mx1 < res.mx2) swap(res.mx1, res.mx2);
return res;
}
void update(int v) {
if (stt.t[v] == Type::Vertex) path[v] = vertex(v);
else if (stt.t[v] == Type::AddVertex) path[v] = add_vertex(point[stt.l[v]], v);
else if (stt.t[v] == Type::Compress) path[v] = compress(path[stt.l[v]], path[stt.r[v]]);
else if (stt.t[v] == Type::AddEdge) point[v] = add_edge(path[stt.l[v]]);
else point[v] = rake(point[stt.l[v]], point[stt.r[v]]);
}
void dfs(int v) {
if (stt.l[v] != -1) dfs(stt.l[v]);
if (stt.r[v] != -1) dfs(stt.r[v]);
update(v);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int q;
ll mw;
cin >> n >> q >> mw;
for (int i = 0;i < n - 1;i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj2[u].push_back({ {i, v}, w });
adj2[v].push_back({ {i, u}, w });
}
dfsd(1);
stt.build();
dfs(stt.root);
ll last = 0;
while (q--) {
int e;
ll w;
cin >> e >> w;
e = (e + last) % (n - 1);
int v = nds[e];
a[v] = (w + last) % mw;
while (v != -1) update(v), v = stt.p[v];
cout << (last = path[stt.root].mx) << '\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... |