이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
#define int ll
struct node {
int val, lazy;
};
struct update {
int x, l, r, ql, qr, id, cent, edgeid;
};
struct edge {
int to; ll cost; int id;
};
vector<update> history[100005];
vector<edge> adj[100005];
int sz[100005];
bool seen[100005];
int timer = 1;
int st[100005], en[100005];
multiset<ll> pathd[100005], total;
int ct = 0;
vector<vector<node>> tree;
ll get() {
return *prev(total.end());
}
ll calc(multiset<ll> &cur) {
if (cur.empty()) return 0;
if (cur.size() == 1) return *cur.begin();
auto itr = cur.end(); itr--;
ll sum = *itr; itr--;
sum += *itr;
return sum;
}
void predfs(int node, int par = -1) {
ct++;
sz[node] = 1;
for (auto nxt : adj[node]) {
if (nxt.to == par)continue;
if (seen[nxt.to]) continue;
predfs(nxt.to, node);
sz[node] += sz[nxt.to];
}
}
int find(int node, int root, int par = -1) {
for (auto nxt : adj[node]) {
if (seen[nxt.to]) continue;
if (nxt.to == par)continue;
if (sz[nxt.to] * 2 > sz[root]) return find(nxt.to, root, node);
}
return node;
}
void dfs(int node, int par = -1) {
st[node] = timer++;
for (auto nxt : adj[node]) {
if (seen[nxt.to] || nxt.to == par) continue;
dfs(nxt.to, node);
}
en[node] = timer - 1;
}
void pushdown(int x, int l, int r, int id) {
if (l == r) return;
tree[id][2 * x].val += tree[id][x].lazy;
tree[id][2 * x].lazy += tree[id][x].lazy;
tree[id][2 * x + 1].val += tree[id][x].lazy;
tree[id][2 * x + 1].lazy += tree[id][x].lazy;
tree[id][x].lazy = 0;
}
void update(int x, int l, int r, int ql, int qr, int id, int cent, int v) {
if (ql <= l && r <= qr) {
if (x == 1) {
pathd[cent].erase(pathd[cent].find(tree[id][x].val));
}
tree[id][x].val += v;
tree[id][x].lazy += v;
if (x == 1) {
pathd[cent].insert(tree[id][x].val);
}
return;
}
if (l > qr || ql > r) return;
pushdown(x, l, r, id);
int mid = (l + r) / 2;
update(2 * x, l, mid, ql, qr, id, cent, v);
update(2 * x + 1, mid + 1, r, ql, qr, id, cent, v);
if (x == 1) {
pathd[cent].erase(pathd[cent].find(tree[id][x].val));
}
tree[id][x].val = max(tree[id][2 * x].val, tree[id][2 * x + 1].val);
if (x == 1) {
pathd[cent].insert(tree[id][x].val);
}
}
void updateall(int node, int par, int cent) {
for (auto nxt : adj[node]) {
if (seen[nxt.to] || par == nxt.to) continue;
update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});
updateall(nxt.to, node, cent);
}
}
void centroid(int node) {
ct = 0;
predfs(node);
if (ct == 1) {
seen[node] = true; return;
}
int cent = find(node, node);
for (auto nxt : adj[cent]) {
if (seen[nxt.to]) continue;
timer = 1;
dfs(nxt.to, cent);
tree.push_back({});
tree.back().resize(4 * (timer + 1));
pathd[cent].insert(0);
update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});
updateall(nxt.to, cent, cent);
}
total.insert(calc(pathd[cent]));
seen[cent] = true;
for (auto nxt : adj[node]) {
if (seen[nxt.to]) continue;
centroid(nxt.to);
}
}
ll edgeinfo[100005];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n, q, w; cin >> n >> q >> w;
for (int i = 1; i <= n-1; i++) {
int a, b; cin >> a >> b;
ll c; cin >> c;
adj[a].push_back({b, c, i});
adj[b].push_back({a, c, i});
edgeinfo[i] = c;
}
centroid(1);
// cout << *prev(total.end()) << endl;
ll last = 0;
for (int i = 0; i < q; i++) {
ll d, e; cin >> d >> e;
d = (d + last) % (n - 1);
d++;
e = (e + last) % w;
ll delta = e - edgeinfo[d];
edgeinfo[d] = e;
for (auto [x, l, r, ql, qr, id, cent, edgeid] : history[d]) {
total.erase(total.find(calc(pathd[cent])));
update(x, l, r, ql, qr, id, cent, delta);
total.insert(calc(pathd[cent]));
}
last = get();
cout << last << "\n";
}
}
# | 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... |