#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<long long, long long>
#define int long long
const int maxn = 2e5 + 5, inf = 1e18;
int lastans;
int n, q, w;
vector<pii> adj[maxn], edge;
map<pii, int> va;
vector<int> dis;
bool vis[maxn];
int dp[4 * maxn][5], st[maxn], fn[maxn];
int h[maxn], lazy[maxn], _h[maxn];
void dfs(int v) {
vis[v] = 1;
st[v] = dis.size();
dis.pb(h[v]);
for (auto[w, u]: adj[v]) {
if (!vis[u]) {
_h[u] = _h[v] + 1;
h[u] = h[v] + w;
dfs(u);
dis.pb(h[v]);
}
}
fn[v] = dis.size() - 1;
}
void updateDP(int id) {
int lc = 2 * id, rc = 2 * id + 1;
dp[id][0] = max({dp[lc][0], dp[rc][0], dp[lc][2] + dp[rc][4], dp[lc][3] + dp[rc][2]});
dp[id][1] = min(dp[lc][1], dp[rc][1]);
dp[id][2] = max(dp[lc][2], dp[rc][2]);
dp[id][3] = max({dp[lc][3], dp[rc][3], dp[lc][2] - (2 * dp[rc][1])});
dp[id][4] = max({dp[lc][4], dp[rc][4], dp[rc][2] - (2 * dp[lc][1])});
}
void printDP(int id, int L, int R) {
cout << L << ", " << R - 1 << ": \n";
cout << "dp[0] = " << dp[id][0] << '\n';
cout << "dp[1] = " << dp[id][1] << '\n';
cout << "dp[2] = " << dp[id][2] << '\n';
cout << "dp[3] = " << dp[id][3] << '\n';
cout << "dp[4] = " << dp[id][4] << '\n';
cout << "\n\n-----------------\n\n";
}
struct segment {
void spread(int id) {
dp[2 * id][1] += lazy[id];
dp[2 * id][2] += lazy[id];
dp[2 * id][3] -= lazy[id];
dp[2 * id][4] -= lazy[id];
dp[2 * id + 1][1] += lazy[id];
dp[2 * id + 1][2] += lazy[id];
dp[2 * id + 1][3] -= lazy[id];
dp[2 * id + 1][4] -= lazy[id];
lazy[2 * id] += lazy[id];
lazy[2 * id + 1] += lazy[id];
lazy[id] = 0;
}
void init(int id, int L, int R) {
if (L + 1 == R) {
dp[id][1] = dis[L];
dp[id][2] = dis[L];
// printDP(id, L, R);
return;
}
int mid = (R + L) >> 1;
init(2 * id, L, mid);
init(2 * id + 1, mid, R);
updateDP(id);
// printDP(id, L, R);
}
void update(int id, int L, int R, int l, int r, int val) {
if (L == l and R == r) {
dp[id][1] += val;
dp[id][2] += val;
dp[id][3] -= val;
dp[id][4] -= val;
lazy[id] += val;
return;
}
spread(id);
int mid = (R + L) >> 1;
if (l < mid) {
update(2 * id, L, mid, l, min(r, mid), val);
}
if (r > mid) {
update(2 * id + 1, mid, R, max(l, mid), r, val);
}
updateDP(id);
// printDP(id, L, R);
}
} seg;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt", "r", stdin);
// freopen("wrong.txt", "w", stdout);
for (int i = 0; i < maxn; i++) {
for (int j = 0; j < 5; j++) {
dp[i][j] = (j == 1 ? inf : 0 - inf);
}
}
cin >> n >> q >> w;
for (int i = 1; i < n; i++) {
int u, v, _w;
cin >> u >> v >> _w;
adj[v].pb({_w, u});
adj[u].pb({_w, v});
va[{u, v}] = _w;
va[{v, u}] = _w;
edge.pb({u, v});
}
dis.pb(-1);
dfs(1);
seg.init(1, 1, 2 * n);
while (q--) {
int i, x;
cin >> i >> x;
// i = (i + lastans) % (n - 1);
// x = (x + lastans) % w;
int u = edge[i].first, v = edge[i].second;
if (_h[u] < _h[v]) {
swap(u, v);
} // h[u] > h[v]
seg.update(1, 1, 2 * n, st[u], fn[u] + 1, x - va[{u, v}]);
cout << max(dp[1][0], dp[1][2]) << '\n';
lastans = max(dp[1][0], dp[1][2]);
va[{u, v}] = x;
va[{v, u}] = x;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
116248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
