| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 430335 | jhwest2 | Dynamic Diameter (CEOI19_diameter) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pint;
const int M = 1 << 17, N = 20;
lint n, q, w, X[M], Y[M], W[M];
pint operator+(const pint &a, const pint &b) {
if (a.va > b.va) return pint(a.va, max(a.vb, b.va));
return pint(b.va, max(a.va, b.vb));
}
struct SEG {
pint T[M << 2]; lint L[M << 2];
void push(int lo, int hi, int idx) {
if (!L[idx]) return;
T[idx].va += L[idx];
if (lo != hi) {
T[idx].vb += L[idx];
L[idx << 1] += L[idx];
L[idx << 1 | 1] += L[idx];
}
L[idx] = 0;
}
pint update(int a, int b, lint x, int lo = 1, int hi = n, int idx = 1) {
push(lo, hi, idx);
if (b < lo || a > hi) return T[idx];
if (a <= lo && hi <= b) {
L[idx] += x; push(lo, hi, idx); return T[idx];
}
return T[idx] = update(a, b, x, lo, lo + hi >> 1, idx << 1) +
update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
}
pint query(int a, int b, int lo = 1, int hi = n, int idx = 1) {
push(lo, hi, idx);
if (b < lo || a > hi) return pint(0, 0);
if (a <= lo && hi <= b) return T[idx];
return query(a, b, lo, lo + hi >> 1, idx << 1) +
query(a, b, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
}
} S[N], T[N], Ans;
int Sub[M], Chk[M], in, jn;
int At[N][M], Col[N][M], Dep[N][M], L[N][M], R[N][M], B[N][M], Lo[M], Hi[M];
lint A[N][M];
vector<pint> G[M];
void dfs(int p, int cur) {
Sub[cur] = 1;
for (auto [d, x] : G[cur]) if (p != x && !Chk[x]) {
dfs(cur, x); Sub[cur] += Sub[x];
}
}
int cent(int p, int cur, int s) {
for (auto [d, x] : G[cur]) if (p != x && !Chk[x]) {
if (Sub[x] > s / 2) return cent(cur, x, s);
}
return cur;
}
void dfs2(int p, int cur, int d, int r, int k, lint dist) {
At[d][cur] = r; L[d][cur] = ++in; Col[d][cur] = k;
S[d].update(in, in, dist);
for (auto [w, x] : G[cur]) if (p != x && !Chk[x]) {
Dep[d][x] = Dep[d][cur] + 1;
dfs2(cur, x, d, r, k, dist + w);
}
R[d][cur] = in;
}
void init() {
queue<pint> Q; Q.emplace(0, 1);
int p = 0;
while (!Q.empty()) {
auto [d, k] = Q.front(); Q.pop();
if (p != d) {
in = jn = 0; p = d;
}
dfs(k, k); k = cent(k, k, Sub[k]);
L[d][k] = ++in; Col[d][k] = k; At[d][k] = k; Lo[k] = jn + 1;
for (auto [w, x] : G[k]) if (!Chk[x]) {
B[d][x] = ++jn;
dfs2(k, x, d, k, x, w);
Q.emplace(d + 1, x);
A[d][x] = S[d].query(L[d][x], R[d][x]).va;
T[d].update(jn, jn, A[d][x]);
}
R[d][k] = in; Chk[k] = 1; Hi[k] = jn;
pint v = T[d].query(Lo[k], Hi[k]);
Ans.update(k, k, v.va + v.vb);
}
}
void update(int u, int v, lint w) {
for (int i = 0; i < N; i++) {
if (At[i][u] != At[i][v]) break;
if (L[i][u] > L[i][v]) swap(u, v);
S[i].update(L[i][v], R[i][v], w);
int x = Col[i][v], r = At[i][v], j = B[i][x];
A[i][x] = S[i].query(L[i][x], R[i][x]).va;
T[i].update(j, j, A[i][x] - T[i].query(j, j).va);
pint v = T[i].query(Lo[r], Hi[r]);
Ans.update(r, r, v.va + v.vb - Ans.query(r, r).va);
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> q >> w;
for (int i = 0; i + 1 < n; i++) {
cin >> X[i] >> Y[i] >> W[i];
G[X[i]].emplace_back(W[i], Y[i]);
G[Y[i]].emplace_back(W[i], X[i]);
}
init();
lint last = 0;
for (int i = 0; i < q; i++) {
lint k, x; cin >> k >> x;
k = (k + last) % (n - 1); x = (x + last) % w;
int u = X[k], v = Y[k];
update(u, v, x - W[k]); W[k] = x;
last = Ans.query(1, n).va; cout << last << '\n';
}
}