#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll
const ll MAXN = 1e5 + 10;
const ll LOG = 20;
const ll INF = 1e18;
int n, q, t, cent_par[MAXN], H[MAXN], D[MAXN][LOG], sz[MAXN],
tin[MAXN][LOG], tout[MAXN][LOG], EV[MAXN], EU[MAXN];
ll w, lz[MAXN * LOG * 4], ans[MAXN], EW[MAXN];
pair<pll, pll> A[MAXN], sg[MAXN * LOG * 4];
vector<pll> adj[MAXN];
bool B[MAXN];
int dfs_sz(int v, int p) {
sz[v] = 1;
for (auto [u, w] : adj[v])
if (!B[u] && u != p)
sz[v] += dfs_sz(u, v);
return sz[v];
}
int centroid(int v, int p, int tn) {
for (auto [u, w] : adj[v])
if (!B[u] && u != p && sz[u] * 2 > tn)
return centroid(u, v, tn);
return v;
}
void dfs(int v, int p, int lvl, ll d, int typ) {
tin[v][lvl] = ++t;
A[t] = {{d, typ}, {-INF, -1}};
D[v][lvl] = D[p][lvl] + 1;
for (auto [u, w] : adj[v])
if (!B[u] && u != p)
dfs(u, v, lvl, d + w, typ);
tout[v][lvl] = t;
}
void build_tree(int v, int p, int lvl) {
v = centroid(v, 0, dfs_sz(v, 0));
cent_par[v] = p;
H[v] = lvl;
B[v] = true;
tin[v][lvl] = ++t;
D[v][lvl] = 0;
A[t] = {{0, v}, {-INF, -1}};
for (auto [u, w] : adj[v])
if (!B[u])
dfs(u, v, lvl, w, u);
tout[v][lvl] = t;
for (auto [u, w] : adj[v])
if (!B[u])
build_tree(u, v, lvl + 1);
}
inline void push(int v) {
sg[v].X.X += lz[v];
sg[v].Y.X += lz[v];
if (v < (MAXN * LOG * 4))
lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];
lz[v] = 0;
}
inline void add(pair<pll, pll>& a, pll b) {
if (b.X > a.X.X) {
if (b.Y != a.X.Y) a.Y = a.X;
a.X = b;
} else if (b.X > a.Y.X && b.Y != a.X.Y) {
a.Y = b;
}
}
inline pair<pll, pll> merge(pair<pll, pll> a, pair<pll, pll> b) {
add(a, b.X);
add(a, b.Y);
return a;
}
void build(int l = 1, int r = t, int v = 1) {
if (l == r) sg[v] = A[l];
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}
}
void update(int ql, int qr, ll val, int l = 1, int r = t, int v = 1) {
push(v);
if (ql > r || qr < l) return;
if (ql <= l && qr >= r) {
lz[v] += val;
push(v);
return;
}
int mid = (l + r) >> 1;
update(ql, qr, val, l, mid, v << 1);
update(ql, qr, val, mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}
pair<pll, pll> query(int ql, int qr, int l = 1, int r = t, int v = 1) {
push(v);
if (ql > r || qr < l) return {{-INF, -INF}, {-INF, -INF - 1}};
if (ql <= l && qr >= r) return sg[v];
int mid = (l + r) >> 1;
return merge(query(ql, qr, l, mid, v << 1),
query(ql, qr, mid + 1, r, v << 1 | 1));
}
set<pll> ans_st;
void update_ans(int v) {
ans_st.erase({ans[v], v});
auto e = query(tin[v][H[v]], tout[v][H[v]]);
ans[v] = max(max(0ll, e.X.X), e.X.X + e.Y.X);
ans_st.insert({ans[v], v});
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q >> w;
for (int i = 0; i < n - 1; i++) {
cin >> EV[i] >> EU[i] >> EW[i];
adj[EU[i]].push_back({EV[i], EW[i]});
adj[EV[i]].push_back({EU[i], EW[i]});
}
build_tree(1, 0, 0);
build();
for (int v = 1; v <= n; v++) update_ans(v);
ll last = 0;
while (q--) {
ll td, tw, ind, delta, rw, u, v;
cin >> td >> tw;
ind = (td + last) % (n - 1), rw = (tw + last) % w;
u = EU[ind], v = EV[ind];
delta = (rw - EW[ind]);
EW[ind] = rw;
if (H[u] > H[v]) swap(u, v);
int c = u;
while (c) {
int au = u, av = v, lvl = H[c];
if (D[au][lvl] > D[av][lvl]) swap(au, av);
update(tin[av][lvl], tout[av][lvl], delta);
update_ans(c);
c = cent_par[c];
}
last = ans_st.rbegin() -> X;
cout << last << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2720 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
1 ms |
2772 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
1 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2772 KB |
Output is correct |
17 |
Correct |
3 ms |
2824 KB |
Output is correct |
18 |
Correct |
2 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2720 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
1 ms |
2772 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
1 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2772 KB |
Output is correct |
17 |
Correct |
3 ms |
2824 KB |
Output is correct |
18 |
Correct |
2 ms |
2900 KB |
Output is correct |
19 |
Correct |
27 ms |
4356 KB |
Output is correct |
20 |
Correct |
28 ms |
4388 KB |
Output is correct |
21 |
Correct |
33 ms |
4428 KB |
Output is correct |
22 |
Correct |
39 ms |
5260 KB |
Output is correct |
23 |
Correct |
44 ms |
13132 KB |
Output is correct |
24 |
Correct |
60 ms |
13508 KB |
Output is correct |
25 |
Correct |
70 ms |
13936 KB |
Output is correct |
26 |
Correct |
79 ms |
14288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
9 ms |
2772 KB |
Output is correct |
5 |
Correct |
41 ms |
3104 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
13 ms |
3284 KB |
Output is correct |
11 |
Correct |
61 ms |
3720 KB |
Output is correct |
12 |
Correct |
7 ms |
7636 KB |
Output is correct |
13 |
Correct |
7 ms |
7764 KB |
Output is correct |
14 |
Correct |
8 ms |
7764 KB |
Output is correct |
15 |
Correct |
23 ms |
7816 KB |
Output is correct |
16 |
Correct |
86 ms |
8236 KB |
Output is correct |
17 |
Incorrect |
131 ms |
90992 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4308 KB |
Output is correct |
2 |
Correct |
49 ms |
4428 KB |
Output is correct |
3 |
Correct |
222 ms |
4656 KB |
Output is correct |
4 |
Correct |
427 ms |
5052 KB |
Output is correct |
5 |
Incorrect |
39 ms |
25032 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
575 ms |
489252 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2720 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
1 ms |
2772 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
1 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2772 KB |
Output is correct |
17 |
Correct |
3 ms |
2824 KB |
Output is correct |
18 |
Correct |
2 ms |
2900 KB |
Output is correct |
19 |
Correct |
27 ms |
4356 KB |
Output is correct |
20 |
Correct |
28 ms |
4388 KB |
Output is correct |
21 |
Correct |
33 ms |
4428 KB |
Output is correct |
22 |
Correct |
39 ms |
5260 KB |
Output is correct |
23 |
Correct |
44 ms |
13132 KB |
Output is correct |
24 |
Correct |
60 ms |
13508 KB |
Output is correct |
25 |
Correct |
70 ms |
13936 KB |
Output is correct |
26 |
Correct |
79 ms |
14288 KB |
Output is correct |
27 |
Correct |
2 ms |
2772 KB |
Output is correct |
28 |
Correct |
2 ms |
2772 KB |
Output is correct |
29 |
Correct |
2 ms |
2772 KB |
Output is correct |
30 |
Correct |
9 ms |
2772 KB |
Output is correct |
31 |
Correct |
41 ms |
3104 KB |
Output is correct |
32 |
Correct |
1 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
3156 KB |
Output is correct |
34 |
Correct |
2 ms |
3156 KB |
Output is correct |
35 |
Correct |
3 ms |
3156 KB |
Output is correct |
36 |
Correct |
13 ms |
3284 KB |
Output is correct |
37 |
Correct |
61 ms |
3720 KB |
Output is correct |
38 |
Correct |
7 ms |
7636 KB |
Output is correct |
39 |
Correct |
7 ms |
7764 KB |
Output is correct |
40 |
Correct |
8 ms |
7764 KB |
Output is correct |
41 |
Correct |
23 ms |
7816 KB |
Output is correct |
42 |
Correct |
86 ms |
8236 KB |
Output is correct |
43 |
Incorrect |
131 ms |
90992 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |