제출 #1249069

#제출 시각아이디문제언어결과실행 시간메모리
1249069cpdreamerDynamic Diameter (CEOI19_diameter)C++20
100 / 100
181 ms56360 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 1e5 + 9; struct node { long long a = 0, b = 0, c = 0, d = 0, e = 0; node operator+(const node &oth) const { node ret; ret.a = max(a, oth.a); ret.b = max(b, oth.b); ret.c = max(max(c, oth.c), a + oth.b); ret.d = max(max(d, oth.d), b + oth.a); ret.e = max(max(e, oth.e), max(c + oth.a, a + oth.d)); return ret; } }; struct ST { #define lc (n << 1) #define rc ((n << 1) | 1) long long lazy[4 * N * 2]; node t[4 * N * 2]; ST() { fill(lazy, lazy + 4 * N * 2, 0); } inline void push(int n, int b, int e) { if (lazy[n] == 0) return; long long v = lazy[n]; t[n].a += v; t[n].b -= 2 * v; t[n].c -= v; t[n].d -= v; if (b != e) { lazy[lc] += v; lazy[rc] += v; } lazy[n] = 0; } inline void pull(int n) { t[n] = t[lc] + t[rc]; } void build(int n, int b, int e, const vector<long long>& dist, const vector<int>& q) { if (b == e) { t[n].a = dist[q[b]]; t[n].b = -2 * dist[q[b]]; t[n].c = -dist[q[b]]; t[n].d = -dist[q[b]]; t[n].e = 0; return; } int mid = (b + e) >> 1; build(lc, b, mid, dist, q); build(rc, mid + 1, e, dist, q); pull(n); } void upd(int n, int b, int e, int i, int j, long long v) { push(n, b, e); if (j < b || e < i) return; if (i <= b && e <= j) { lazy[n] += v; push(n, b, e); return; } int mid = (b + e) >> 1; upd(lc, b, mid, i, j, v); upd(rc, mid + 1, e, i, j, v); pull(n); } } t; long long W[N]; vector<pair<int, int>> g[N]; int T, st[N * 2], en[N * 2], pos[N]; vector<long long> dist; vector<int> q_nodes; void dfs(int u, int p = 0, long long current_dist = 0) { st[u] = ++T; q_nodes[T] = u; dist[u] = current_dist; for (auto e : g[u]) { int v = e.first, i = e.second; if (v == p) continue; pos[i] = v; dfs(v, u, current_dist + W[i]); q_nodes[++T] = u; } en[u] = T; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; long long mod; cin >> n >> q >> mod; dist.resize(n + 1); q_nodes.resize(2 * n); for (int i = 1; i < n; i++) { int u, v; long long w; cin >> u >> v >> w; g[u].push_back({v, i}); g[v].push_back({u, i}); W[i] = w; } T = 0; dfs(1); t.build(1, 1, T, dist, q_nodes); long long last = 0; while (q--) { int d; long long e; cin >> d >> e; d = (d + last) % (n - 1) + 1; e = (e + last) % mod; t.upd(1, 1, T, st[pos[d]], en[pos[d]], e - W[d]); W[d] = e; last = t.t[1].e; cout << last << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...