//1L1YA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Pb push_back
#define dokme(x) cout << x << endl, exit(0)
#define pll pair<ll,ll>
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lc id<<1
#define rc lc|1
const ll mod=1e9+7;
const ll oo=4e18;
const int N=1e5+5;
const int lg=23;
ll n,q,W,T,lst,a[N],h[N],st[N],et[N],wp[N],par[N],lz[N<<2];
pll seg[N<<2];
vector<pll> E,adj[N];
void shift(int id){
seg[lc].F+=lz[id];lz[lc]+=lz[id];
seg[rc].F+=lz[id];lz[rc]+=lz[id];
lz[id]=0;
}
void modify(int pos,ll val,int id=1,int l=1,int r=n+1){
if(r-l==1){
seg[id].F=val;
seg[id].S=l;
return;
}
int mid=l+r>>1;
if(pos<mid) modify(pos,val,lc,l,mid);
else modify(pos,val,rc,mid,r);
if(seg[lc].F>seg[rc].F) seg[id]=seg[lc];
else seg[id]=seg[rc];
}
void update(int ql,int qr,ll val,int id=1,int l=1,int r=n+1){
if(qr<=l || ql>=r) return;
if(ql<=l && r<=qr){
seg[id].F+=val;
lz[id]+=val;
return;
}
int mid=l+r>>1;
shift(id);
update(ql,qr,val,lc,l,mid);
update(ql,qr,val,rc,mid,r);
if(seg[lc].F>seg[rc].F) seg[id]=seg[lc];
else seg[id]=seg[rc];
}
pll get(int ql,int qr,int id=1,int l=1,int r=n+1){
if(qr<=l || ql>=r) return {-1,0};
if(ql<=l && r<=qr) return seg[id];
int mid=l+r>>1;
shift(id);
pll p1=get(ql,qr,lc,l,mid),p2=get(ql,qr,rc,mid,r);
if(p1.F>p2.F) return p1;
else return p2;
}
void dfs(int v,int p=-1){
st[v]=T++;
a[st[v]]=v;
for(auto [u,w]: adj[v])
if(u!=p){
h[u]=h[v]+w;
par[u]=v;
wp[u]=w;
dfs(u,v);
}
et[v]=T;
}
void calc(){
pll p=get(1,n+1);
int v=a[p.S];
int l=0,r=adj[1].size();
while(r-l>1){
int mid=l+r>>1;
if(st[adj[1][l].F]<=st[v]) l=mid;
else r=mid;
}
int u=adj[1][l].F;
ll ans=0;
ans=max(ans,get(1,st[u]).F);
if(et[u]!=n+1)
ans=max(ans,get(et[u],n+1).F);
ans=ans+p.F;
cout << ans << endl;
lst=ans;
}
int main(){
FastIO
cin >> n >> q >> W;
for(int i=1;i<n;i++){
ll u,v,w;
cin >> u >> v >> w;
adj[u].Pb({v,w});
adj[v].Pb({u,w});
E.Pb({u,v});
}
T=1;
dfs(1);
for(int i=1;i<=n;i++)
modify(st[i],h[i]);
for(int i=1;i<n;i++)
if(E[i].F!=par[E[i].S])
swap(E[i].F,E[i].S);
while(q--){
ll i,x;
cin >> i >> x;
i=(i+lst)%(n-1);
x=(x+lst)%W;
int u=E[i].F,v=E[i].S;
update(st[v],et[v],x-wp[v]);
wp[v]=x;
calc();
}
return 0;
}
Compilation message
diameter.cpp: In function 'void modify(int, long long int, int, int, int)':
diameter.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid=l+r>>1;
| ~^~
diameter.cpp: In function 'void update(int, int, long long int, int, int, int)':
diameter.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid=l+r>>1;
| ~^~
diameter.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, int, int)':
diameter.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid=l+r>>1;
| ~^~
diameter.cpp: In function 'void calc()':
diameter.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid=l+r>>1;
| ~^~
diameter.cpp: In function 'int main()':
diameter.cpp:125:13: warning: unused variable 'u' [-Wunused-variable]
125 | int u=E[i].F,v=E[i].S;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
8792 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
27744 KB |
Output is correct |
2 |
Incorrect |
150 ms |
27804 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |