using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <memory.h>
#include <vector>
#include <bitset>
typedef pair<int,int> pii;
typedef long long LL;
#define iter(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#define mkp make_pair
#include <climits>
const int maxn = 1e5+100,mod = 0;
struct EDGE{
int u,v;
LL w;
EDGE(int u,int v,LL w):u(u), v(v), w(w){}
EDGE(){}
}edge[maxn];
vector <pair<int,LL>> adj[maxn];
int father[maxn];
pii seg[maxn];
LL mx[maxn];
#define mid (LB+RB)/2
struct segtree{
vector <LL> arr,mx,lazy;
segtree(){
arr.resize(1);
}
void maketree(int cur,int LB,int RB){
if (LB == RB) mx[cur] = arr[LB];
else{
maketree(cur*2,LB,mid);
maketree(cur*2+1,mid+1,RB);
mx[cur] = max(mx[cur*2],mx[cur*2+1]);
}
}
void mt(){
mx.resize(arr.size()*4);
lazy.resize(arr.size()*4);
maketree(1,1,arr.size()-1);
}
void push(int cur,int LB,int RB){
if (lazy[cur]){
mx[cur] += lazy[cur];
if (LB != RB){
lazy[cur*2] += lazy[cur];
lazy[cur*2+1] += lazy[cur];
}
lazy[cur] = 0;
}
}
void ru(int l,int r,LL val,int cur,int LB,int RB){
push(cur,LB,RB);
if (l == LB and r == RB){
lazy[cur] += val;
push(cur,LB,RB);
return;
}
if (r <= mid) ru(l,r,val,cur*2,LB,mid);
else if (l > mid) ru(l,r,val,cur*2+1,mid+1,RB);
else{
ru(l,mid,val,cur*2,LB,mid);
ru(mid+1,r,val,cur*2+1,mid+1,RB);
}
push(cur*2,LB,mid);
push(cur*2+1,mid+1,RB);
mx[cur] = max(mx[cur*2],mx[cur*2+1]);
}
LL rq(int l,int r,int cur,int LB,int RB){
push(cur,LB,RB);
if (l == LB and r == RB) return mx[cur];
if (r <= mid) return rq(l,r,cur*2,LB,mid);
else if (l > mid) return rq(l,r,cur*2+1,mid+1,RB);
else return max(rq(l,mid,cur*2,LB,mid),rq(mid+1,r,cur*2+1,mid+1,RB));
}
void upd(int l,int r,LL val){
ru(l,r,val,1,1,arr.size()-1);
}
LL query(int l,int r){
return rq(l,r,1,1,arr.size()-1);
}
};
vector <segtree> st;
int belong[maxn],treecnt;
pii dfs(int x,int fr,LL dis,int sti){
father[x] = fr;
belong[x] = sti;
pii r = {};
if (adj[x].size() == 1){
r = mkp(int(st[sti].arr.size()),int(st[sti].arr.size()));
st[sti].arr.pb(dis);
}
else
for (auto [i,w]:adj[x]) if (i != fr){
if (!r.F) r = dfs(i,x,dis + w,sti);
else r.S = dfs(i,x,dis + w,sti).S;
}
seg[x] = r;
return r;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n,q;
LL w;
cin >> n >> q >> w;
for (int i=0;i<n-1;++i){
int u,v; LL c;
cin >> u >> v >> c;
edge[i] = EDGE(u,v,c);
adj[u].pb(mkp(v,c));
adj[v].pb(mkp(u,c));
}
st.resize(adj[1].size());
multiset <LL> ms;
for (auto [i,d]:adj[1]){
dfs(i,1,d,treecnt);
st[treecnt].mt();
mx[treecnt] = st[treecnt].mx[1];
ms.insert(mx[treecnt]);
++treecnt;
}
for (int i=0;i<n-1;++i){
if (edge[i].u == father[edge[i].v])
swap(edge[i].u,edge[i].v);
}
LL last = 0;
while (q--){
LL d,e;
cin >> d >> e;
d = (last + d) % (n-1);
e = (last + e) % w;
LL dif = e - edge[d].w;
int m = edge[d].u;
edge[d].w = e;
ms.erase(ms.find(mx[belong[m]]));
st[belong[m]].upd(seg[m].F,seg[m].S,dif);
mx[belong[m]] = st[belong[m]].mx[1];
ms.insert(mx[belong[m]]);
last = *prev(ms.end()) + (ms.size() > 1 ? *prev(prev(ms.end())) : 0);
cout /*<< d << ' ' << e << ' '*/ << last << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
3 ms |
2636 KB |
Output is correct |
4 |
Correct |
13 ms |
2764 KB |
Output is correct |
5 |
Correct |
98 ms |
2996 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2764 KB |
Output is correct |
8 |
Correct |
2 ms |
2764 KB |
Output is correct |
9 |
Correct |
3 ms |
2892 KB |
Output is correct |
10 |
Correct |
12 ms |
2960 KB |
Output is correct |
11 |
Correct |
53 ms |
3232 KB |
Output is correct |
12 |
Correct |
6 ms |
4556 KB |
Output is correct |
13 |
Correct |
7 ms |
4556 KB |
Output is correct |
14 |
Correct |
8 ms |
4556 KB |
Output is correct |
15 |
Correct |
20 ms |
4720 KB |
Output is correct |
16 |
Correct |
71 ms |
5028 KB |
Output is correct |
17 |
Correct |
137 ms |
41756 KB |
Output is correct |
18 |
Correct |
143 ms |
41736 KB |
Output is correct |
19 |
Correct |
187 ms |
41776 KB |
Output is correct |
20 |
Correct |
177 ms |
41924 KB |
Output is correct |
21 |
Correct |
396 ms |
42412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
227 ms |
15580 KB |
Output is correct |
2 |
Correct |
186 ms |
15632 KB |
Output is correct |
3 |
Correct |
235 ms |
16960 KB |
Output is correct |
4 |
Correct |
264 ms |
20016 KB |
Output is correct |
5 |
Correct |
197 ms |
22220 KB |
Output is correct |
6 |
Correct |
227 ms |
33492 KB |
Output is correct |
7 |
Correct |
218 ms |
22144 KB |
Output is correct |
8 |
Correct |
229 ms |
22180 KB |
Output is correct |
9 |
Correct |
198 ms |
22064 KB |
Output is correct |
10 |
Correct |
212 ms |
22256 KB |
Output is correct |
11 |
Correct |
214 ms |
24384 KB |
Output is correct |
12 |
Correct |
226 ms |
35100 KB |
Output is correct |
13 |
Correct |
145 ms |
24388 KB |
Output is correct |
14 |
Correct |
178 ms |
24384 KB |
Output is correct |
15 |
Correct |
147 ms |
24352 KB |
Output is correct |
16 |
Correct |
195 ms |
24592 KB |
Output is correct |
17 |
Correct |
197 ms |
26504 KB |
Output is correct |
18 |
Correct |
224 ms |
35716 KB |
Output is correct |
19 |
Correct |
152 ms |
24364 KB |
Output is correct |
20 |
Correct |
134 ms |
24268 KB |
Output is correct |
21 |
Correct |
215 ms |
24388 KB |
Output is correct |
22 |
Correct |
170 ms |
24572 KB |
Output is correct |
23 |
Correct |
170 ms |
26408 KB |
Output is correct |
24 |
Correct |
170 ms |
35744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |