/* In the name of God */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;
inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }
const int MAXN = 1e5 + 5, LG = 20;
int h[MAXN], par[MAXN][LG];
int st[MAXN], et[MAXN], timer = 1;
ll wei[MAXN];
ll dp[MAXN];
vector<PII> N[MAXN];
VI ord = {23};
void dfs_ini(int v, int p){
ord.PB(v);
st[v] = timer++;
for (auto [u, e] : N[v]){
if (u == p) continue;
h[u] = h[v] + 1;
par[u][0] = v;
for (int i = 1; i < LG; i++){
par[u][i] = par[par[u][i - 1]][i - 1];
}
dp[u] = dp[v] + wei[e];
dfs_ini(u, v);
}
et[v] = timer;
}
PII edg[MAXN];
ll seg[MAXN << 2], laz[MAXN << 2];
#define lc id << 1
#define rc id << 1 | 1
void build(int id, int l, int r){
if (r - l == 1){
seg[id] = dp[ord[l]];
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid, r);
seg[id] = max(seg[lc], seg[rc]);
}
void shift(int id, int l, int r){
laz[lc] += laz[id];
laz[rc] += laz[id];
seg[lc] += laz[id];
seg[rc] += laz[id];
laz[id] = 0;
}
void upd(int id, int l, int r, int ql, int qr, ll val){
if (ql >= r || qr <= l) return;
if (l >= ql && r <= qr){
seg[id] += val;
laz[id] += val;
return;
}
int mid = l + r >> 1;
shift(id, l, r);
upd(lc, l, mid, ql, qr, val);
upd(rc, mid, r, ql, qr, val);
seg[id] = max(seg[lc], seg[rc]);
}
ll get(int id, int l, int r, int ql, int qr){
if (ql >= r || qr <= l) return 0;
if (l >= ql && r <= qr) return seg[id];
int mid = l + r >> 1;
shift(id, l, r);
return max(get(lc, l, mid, ql, qr), get(rc, mid, r, ql, qr));
}
int goo(int v, int k){
for (int i = 0; i < LG; i++){
if (k >> i & 1) v = par[v][i];
}
return v;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q, w;
cin >> n >> q >> w;
for (int i = 1; i < n; i++){
int u, v;
cin >> u >> v >> wei[i];
N[u].PB(MP(v, i));
N[v].PB(MP(u, i));
edg[i] = MP(u, v);
}
for (int i = 0; i < LG; i++) par[1][i] = 1;
dfs_ini(1, 0);
build(1, 1, n + 1);
set<pair<ll, int>> S;
S.insert(MP(0, 0));
for (auto [u, e] : N[1]){
ll val = get(1, 1, n + 1, st[u], et[u]);
S.insert(MP(-val, u));
//dbg2(u, get(1, 1, n + 1, st[u], et[u]));
}
//dbg("ADF");
//for (auto [x, y] : S) dbg2(-x, y);
ll lst = 0;
while (q--){
ll d, e;
cin >> d >> e;
(d += lst) %= (n - 1);
(e += lst) %= w;
d++;
int v = (h[edg[d].first] < h[edg[d].second] ? edg[d].first : edg[d].second);
int u = edg[d].first + edg[d].second - v;
int bache = goo(u, h[u] - h[1] - 1);
ll prvbache = get(1, 1, n + 1, st[bache], et[bache]);
S.erase(MP(-prvbache, bache));
upd(1, 1, n + 1, st[u], et[u], e - wei[d]);
ll cur = get(1, 1, n + 1, st[bache], et[bache]);
S.insert(MP(-cur, bache));
//for (auto [x, y] : S) dbg2(-x, y);
if (S.empty()) break;
auto x = *S.begin();
S.erase(S.begin());
if (S.empty()) break;
ll ans = -x.first + -(*S.begin()).first;
cout << ans << endl;
//dbg(ans);
lst = ans;
S.insert(x);
wei[d] = e;
/*dbg(goo(u, h[u] - h[1] - 1));
for (auto [u, e] : N[1]){
dbg2(u, get(1, 1, n + 1, st[u], et[u]));
}
dbg("ADF");*/
//lst = dp[1][0];
}
return 0;
}
Compilation message
diameter.cpp: In function 'void build(int, int, int)':
diameter.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In function 'void upd(int, int, int, int, int, ll)':
diameter.cpp:88:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In function 'll get(int, int, int, int, int)':
diameter.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid = l + r >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
11 ms |
10804 KB |
Output is correct |
5 |
Correct |
50 ms |
10976 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
2 ms |
10588 KB |
Output is correct |
9 |
Correct |
3 ms |
10588 KB |
Output is correct |
10 |
Correct |
16 ms |
10808 KB |
Output is correct |
11 |
Correct |
72 ms |
11172 KB |
Output is correct |
12 |
Correct |
4 ms |
11356 KB |
Output is correct |
13 |
Correct |
5 ms |
11356 KB |
Output is correct |
14 |
Correct |
6 ms |
11356 KB |
Output is correct |
15 |
Correct |
22 ms |
11420 KB |
Output is correct |
16 |
Correct |
92 ms |
11860 KB |
Output is correct |
17 |
Correct |
89 ms |
30804 KB |
Output is correct |
18 |
Correct |
86 ms |
30844 KB |
Output is correct |
19 |
Correct |
78 ms |
30880 KB |
Output is correct |
20 |
Correct |
108 ms |
30916 KB |
Output is correct |
21 |
Correct |
266 ms |
31340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
5 ms |
8796 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |