| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1305444 | vtnoo | Dynamic Diameter (CEOI19_diameter) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC optimize("inline")
#pragma GCC target("avx2","sse4.2","popcnt")
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
#define int long long
const int MAXN=1e5+9, INF=1e18;
vector<pair<int,int>>adj[MAXN];
vector<int>st[MAXN],lz[MAXN];
unordered_map<int,int>in[MAXN],out[MAXN],rc[MAXN],sig[MAXN];
multiset<int>ms[MAXN];
multiset<int>m;
int n,tim,sz[MAXN],ew[MAXN],z[MAXN],anc[MAXN],tam[MAXN],bst[MAXN],cen[MAXN];
bool rmv[MAXN];
static inline void apply(int root,int v,int x){
st[root][v]+=x;
lz[root][v]+=x;
}
static inline void push(int root,int v){
apply(root,v*2,lz[root][v]);
apply(root,v*2+1,lz[root][v]);
lz[root][v]=0;
}
static inline void upd(int root,int ts,int te,int x,int s,int e,int v=1){
if(e<ts||te<s)return;
if(ts<=s&&e<=te){
apply(root,v,x);
return;
}else{
push(root,v);
int m=(s+e)/2;
upd(root,ts,te,x,s,m,v*2);
upd(root,ts,te,x,m+1,e,v*2+1);
st[root][v]=max(st[root][v*2],st[root][v*2+1]);
}
}
static inline int que(int root,int ts,int te,int s,int e,int v=1){
if(e<ts||te<s)return -INF;
if(ts<=s&&e<=te){
return st[root][v];
}else{
push(root,v);
int m=(s+e)/2;
return max(que(root,ts,te,s,m,v*2),que(root,ts,te,m+1,e,v*2+1));
}
}
static inline void dfs(int u,int root,int top,vector<int>&c,int p=-1){
in[root][u]=tim++;
c.pb(u);
for(auto&[v,i]:adj[u]){
if(rmv[v]||v==p)continue;
top=(u==root?v:top);
z[v]=ew[i];
rc[root][i]=top;
sig[root][i]=v;
dfs(v,root,top,c,u);
}
out[root][u]=tim-1;
}
static inline int getSizes(int u,int p=-1){
sz[u]=1;
for(auto&[v,i]:adj[u]){
if(rmv[v]||v==p)continue;
sz[u]+=getSizes(v,u);
}
return sz[u];
}
static inline int getCentroid(int u,int treeSize,int p=-1){
for(auto[v,i]:adj[u]){
if(rmv[v]||v==p)continue;
if(sz[v]>treeSize/2)return getCentroid(v,treeSize,u);
}
return u;
}
static inline int centroidDecomposition(int u=1,int p=-1){
int treeSize=getSizes(u);
int centroid=getCentroid(u,treeSize);
//~ cout<<"======================="<<endl;
//~ cout<<centroid<<endl;
rmv[centroid]=true;
vector<int>c;
c.reserve(treeSize);
tim=0;
dfs(centroid,centroid,-1,c);
int nn=1;
while(nn<treeSize)nn*=2;
tam[centroid]=nn;
st[centroid].resize(nn*2,0);
lz[centroid].resize(nn*2,0);
z[centroid]=0;
fore(i,0,SZ(c)){
//~ cout<<c[i]<<" "<<z[c[i]]<<endl;
upd(centroid,in[centroid][c[i]],out[centroid][c[i]],z[c[i]],0,nn-1);
}
//~ cout<<endl;
for(auto[v,i]:adj[centroid]){
if(rmv[v])continue;
//~ cout<<v<<" "<<que(centroid,in[centroid][v],out[centroid][v],0,nn-1)<<endl;
ms[centroid].insert(que(centroid,in[centroid][v],out[centroid][v],0,nn-1));
}
if(p!=-1)anc[centroid]=p;
int ans=0;
if(SZ(ms[centroid])==1)ans=*ms[centroid].begin();
else if(SZ(ms[centroid])>1)ans=*prev(ms[centroid].end())+*prev(prev(ms[centroid].end()));
bst[centroid]=ans;
m.insert(bst[centroid]);
for(auto[v,i]:adj[centroid]){
if(rmv[v])continue;
cen[i]=centroidDecomposition(v,centroid);
}
return centroid;
}
static inline void updCentroidTree(int centroid,int x,int i){
if(centroid==0)return;
ms[centroid].erase(ms[centroid].find(que(centroid,in[centroid][rc[centroid][i]],out[centroid][rc[centroid][i]],0,tam[centroid]-1)));
upd(centroid,in[centroid][sig[centroid][i]],out[centroid][sig[centroid][i]],x,0,tam[centroid]-1);
ms[centroid].insert(que(centroid,in[centroid][rc[centroid][i]],out[centroid][rc[centroid][i]],0,tam[centroid]-1));
int ans=0;
if(SZ(ms[centroid])==1)ans=*ms[centroid].begin();
else ans=*prev(ms[centroid].end())+*prev(prev(ms[centroid].end()));
m.erase(m.find(bst[centroid]));
bst[centroid]=ans;
m.insert(bst[centroid]);
updCentroidTree(anc[centroid],x,i);
}
int32_t main(){FIN;
int q;
ll w;
cin>>n>>q>>w;
fore(i,0,n-1){
int u,v;
ll c;
cin>>u>>v>>c;
adj[u].pb({v,i});
adj[v].pb({u,i});
ew[i]=c;
}
centroidDecomposition();
//~ fore(i,1,n+1)cout<<bst[i]<<" ";
//~ cout<<endl;
//~ if(SZ(ms[5])==1)cout<<*ms[5].begin()<<endl;
//~ else cout<<*prev(ms[5].end())<<"+"<<*prev(prev(ms[5].end()))<<endl;
//~ cout<<*prev(m.end())<<endl;
ll last=0;
while(q--){
ll d_, e_;
cin>>d_>>e_;
ll d=(d_+last)%(n-1);
ll e=(e_+last)%w;
ll diff=e-ew[d];
ew[d]=e;
updCentroidTree(anc[cen[d]],diff,d);
cout<<*prev(m.end())<<endl;
last=*prev(m.end());
}
}