#include <array>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
long long n, q;
long long w;
struct segtree{
int n, height;
vector<long long> tree, lazy;
segtree() {}
segtree(int sz){
n = sz;
height = 32 - __builtin_clz(n);
tree.assign(2 * n, 0);
lazy.assign(n, 0);
}
void build_all(vector<long long>& v){
for (int i = 0; i < v.size(); i++){
tree[n + i] = v[i];
}
for (int i = n - 1; i > 0; --i) tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
void apply(int p, long long value) {
tree[p] += value;
if (p < n) lazy[p] += value;
}
void build(int p) {
while (p > 1) p >>= 1, tree[p] = max(tree[p<<1], tree[p<<1|1]) + lazy[p];
}
void push(int p) {
for (int s = height; s > 0; --s) {
int i = p >> s;
if (lazy[i] != 0) {
apply(i<<1, lazy[i]);
apply(i<<1|1, lazy[i]);
lazy[i] = 0;
}
}
}
void update(int l, int r, long long value) {
l += n, r += n;
int l0 = l, r0 = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) apply(l++, value);
if (r&1) apply(--r, value);
}
build(l0);
build(r0 - 1);
}
int query(int l, int r) {
l += n, r += n;
push(l);
push(r - 1);
long long res = 0;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) res = max(res, tree[l++]);
if (r&1) res = max(tree[--r], res);
}
return res;
}
};
int root;
vector<vector<pair<int, long long>>> adj;
vector<vector<array<int, 3>>> ancestors;
vector<array<long long, 3>> edges;
vector<int> subtree_sz, removed;
vector<segtree> segtrees;
vector<vector<int>> tins, touts;
vector<vector<long long>> tours;
vector<int> timers;
vector<multiset<long long>> max_dists;
multiset<long long> max_diams;
int find_subtree_sz(int v, int p = 0){
subtree_sz[v] = 1;
for (auto [x, w] : adj[v]){
if (x != p && !removed[x])
subtree_sz[v] += find_subtree_sz(x, v);
}
return subtree_sz[v];
}
int find_centroid(int v, int sz, int p = 0){
for (auto [x, w] : adj[v]){
if (x == p || removed[x]) continue;
if (subtree_sz[x] * 2 >= sz)
return find_centroid(x, sz, v);
}
return v;
}
void assign_ancestors(int v, int p, int level, int child_idx, int centroid, int d, long long total_w){
tins[level][v] = timers[level]++;
tours[level][tins[level][v]] = total_w;
ancestors[v].push_back({centroid, d, child_idx});
for (auto [x, w] : adj[v]){
if (removed[x] || x == p) continue;
assign_ancestors(x, v, level, child_idx, centroid, d + 1, total_w + w);
}
touts[level][v] = timers[level];
}
long long get_max_diam(int k){
long long res = 0;
auto it = max_dists[k].rbegin();
res += *it;
res += *next(it);
return res;
}
int build_centroid(int v, int level = 0, int build_ms = 0){
find_subtree_sz(v);
int centroid = find_centroid(v, subtree_sz[v]);
removed[centroid] = 1;
if (!build_ms){
ancestors[centroid].push_back({centroid, 0, -1});
} else {
max_dists[centroid].insert(0);
max_dists[centroid].insert(0);
}
for (auto [x, w] : adj[centroid]){
if (removed[x]) continue;
if (!build_ms){
assign_ancestors(x, centroid, level, x, centroid, 1, w);
} else {
long long diam = segtrees[level].query(tins[level][x], touts[level][x]);
max_dists[centroid].insert(diam);
}
int c = build_centroid(x, level + 1, build_ms);
}
if (build_ms){
max_diams.insert(get_max_diam(centroid));
}
return centroid;
}
void update_multiset(multiset<long long>& mset, long long pre, long long nxt){
auto it = mset.find(pre);
mset.erase(it);
mset.insert(nxt);
}
void update(int k, long long e){
auto& [a, b, w] = edges[k];
long long diff = e - w;
int min_sz = min(ancestors[a].size(), ancestors[b].size());
for (int i = 0; i < min_sz; i++){
if (ancestors[a][i][1] < ancestors[b][i][1]){
swap(a, b);
}
auto [centroid, dist, idx_child] = ancestors[a][i];
// increase a subtree distances by diff
long long pre_max = segtrees[i].query(tins[i][idx_child], touts[i][idx_child]);
segtrees[i].update(tins[i][a], touts[i][a], diff);
long long nxt_max = segtrees[i].query(tins[i][idx_child], touts[i][idx_child]);
if (pre_max == nxt_max)
continue;
// update max_dist[centroid]
long long pre_diam = get_max_diam(centroid);
update_multiset(max_dists[centroid], pre_max, nxt_max);
long long nxt_diam = get_max_diam(centroid);
if (pre_diam == nxt_diam)
continue;
// update max_diams
update_multiset(max_diams, pre_diam, nxt_diam);
}
w = e;
}
long long get_answer(){
return *max_diams.rbegin();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q >> w;
adj.resize(n);
long long a, b, c;
for (int i = 0; i < n-1; i++){
cin >> a >> b >> c;
--a, --b;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
edges.push_back({a, b, c});
}
removed.assign(n, 0);
subtree_sz.assign(n, -1);
ancestors.resize(n);
segtrees.assign(18, segtree(n));
tins.assign(18, vector<int>(n));
touts.assign(18, vector<int>(n));
tours.assign(18, vector<long long>(n));
timers.assign(18, 0);
max_dists.resize(n);
root = build_centroid(0);
for (int i = 0; i < 18; i++){
segtrees[i].build_all(tours[i]);
}
removed.assign(n, 0);
build_centroid(0, 0, 1);
long long last = 0;
long long d, e;
while (q--){
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
update(d, e);
last = get_answer();
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... |