This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<pli,pli> ppli;
#define INF 1000005
int Q;
ll N,W;
vector<int> adj[MAXN];
vector<pair<int,int>> edges;
map<pair<int,int>,ll> w;//each edge is stored with two elements (order of the pair)
ll last;
//centroid decomposition
vector<int> ch[MAXN];
int par[MAXN],sz[MAXN],r[MAXN];
map<pair<int,int>,vector<pair<int,int>>> edge_info;//edge->(centroid,order of child), for the ancestors (O(logN)) worst-case
vector<pair<int,int>> leaf_range[MAXN];//range of leaves for each centroid and for each vertex(vertices are in dfs order)
vector<ll> st[MAXN];//max segment tree for each centroid
vector<ll> lazy[MAXN];
vector<ll> chp_sub[MAXN];//dfs-order->head order
int num_leaf[MAXN];//for each centroid number of leaves
int curcen,dfs_order,leaf_order;
ll leaf_dist[MAXN];//temporary for build centroid st
set<pli,greater<pli>> mxpaths[MAXN];
set<pli,greater<pli>> diams;//holds for each centroid the diameter
vector<ll> order_ch[MAXN];
//segment tree
void build(int c,int v,int start,int end){
if(start==end){
st[c][v]=leaf_dist[start];
lazy[c][v]=0;
return;
}
int mid=(start+end)/2;
build(c,2*v,start,mid);
build(c,2*v+1,mid+1,end);
st[c][v]=max(st[c][2*v],st[c][2*v+1]);
}
void update(int c,int from,int to,ll val,int v,int start,int end){
if(start==from&&end==to){
st[c][v]+=val;
lazy[c][v]+=val;
return;
}
int mid=(start+end)/2;
//propagate
if(lazy[c][v]){
update(c,start,mid,lazy[c][v],2*v,start,mid);
update(c,mid+1,end,lazy[c][v],2*v+1,mid+1,end);
lazy[c][v]=0;
}
if(to<=mid){
update(c,from,to,val,2*v,start,mid);
}else if(from>mid){
update(c,from,to,val,2*v+1,mid+1,end);
}else{
update(c,from,mid,val,2*v,start,mid);
update(c,mid+1,to,val,2*v+1,mid+1,end);
}
st[c][v]=max(st[c][2*v],st[c][2*v+1]);
}
ll query(int c,int from,int to,int v,int start,int end){//for full query: st[c][1]
if(start==from&&end==to){
return st[c][v];
}
int mid=(start+end)/2;
//propagate
if(lazy[c][v]){
update(c,start,mid,lazy[c][v],2*v,start,mid);
update(c,mid+1,end,lazy[c][v],2*v+1,mid+1,end);
lazy[c][v]=0;
}
if(to<=mid){
return query(c,from,to,2*v,start,mid);
}else if(from>mid){
return query(c,from,to,2*v+1,mid+1,end);
}else{
return max(query(c,from,mid,2*v,start,mid),query(c,mid+1,to,2*v+1,mid+1,end));
}
}
void dfs_sz(int curr,int p){
sz[curr]=1;
for(int to:adj[curr]){
if(to==p||r[to]) continue;
dfs_sz(to,curr);
sz[curr]+=sz[to];
}
}
int centroid(int curr,int p,int n){
for(int to:adj[curr]){
if(to==p||r[to]) continue;
if(2*sz[to]>n) return centroid(to,curr,n);
}
return curr;
}
int dfs_cen(int curr,int p,int d,int s,int ch_p){//returns dfs order
int ord=dfs_order++;
chp_sub[curcen].push_back(ch_p?ord:s);
leaf_range[curcen].push_back({INF,0});//placeholder
if(p!=-1){
edge_info[{curr,p}].push_back({curcen,ord});
edge_info[{p,curr}].push_back({curcen,ord});
}
int leaf=1;
for(int to:adj[curr]){
if(to==p||r[to]) continue;
leaf=0;
int ordch=dfs_cen(to,curr,d+w[{curr,to}],ch_p?ord:s,p==-1);
if(p==-1) order_ch[curcen].push_back(ordch);
leaf_range[curcen][ord].first=min(leaf_range[curcen][ord].first,leaf_range[curcen][ordch].first);
leaf_range[curcen][ord].second=max(leaf_range[curcen][ord].second,leaf_range[curcen][ordch].second);
}
if(leaf){
leaf_order++;
leaf_dist[leaf_order]=d;
leaf_range[curcen][ord]={leaf_order,leaf_order};
}
return ord;
}
ll diam(int cen,int ch){
return query(cen,leaf_range[cen][ch].first,leaf_range[cen][ch].second,1,1,num_leaf[cen]);
}
ll tdiam(int cen){
ll d=0;
if(!mxpaths[cen].empty()){
auto it=mxpaths[cen].begin();
d+=it->first;
if(mxpaths[cen].size()>=2){
it++;
d+=it->first;
}
}
return d;
}
//returns centroid
int centroid_decomp(int curr,int p=-1){
dfs_sz(curr,-1);
int cen=centroid(curr,-1,sz[curr]);
curcen=cen;
//now prepare stuff this centroid
dfs_order=0;
leaf_order=0;
dfs_cen(cen,-1,0,0,1);
st[cen]=vector<ll>(4*leaf_order,0);
lazy[cen]=vector<ll>(4*leaf_order,0);
num_leaf[cen]=leaf_order;
build(cen,1,1,num_leaf[cen]);
for(int to:order_ch[cen]){
mxpaths[cen].insert({diam(cen,to),to});
}
diams.insert({tdiam(cen),cen});
//--
r[cen]=1;
par[cen]=p;
for(int to:adj[cen]){
if(r[to]) continue;
int c_to=centroid_decomp(to,cen);
ch[cen].push_back(c_to);
}
return cen;
}
ll query_cen(int a,int b,ll we){
ll diff=we-w[{a,b}];
w[{a,b}]=w[{b,a}]=we;
auto changes=edge_info[{a,b}];
for(auto p:changes){
int cen,ord;
tie(cen,ord)=p;
diams.erase({tdiam(cen),cen});
mxpaths[cen].erase({diam(cen,chp_sub[cen][ord]),chp_sub[cen][ord]});
update(cen,leaf_range[cen][ord].first,leaf_range[cen][ord].second,diff,1,1,num_leaf[cen]);
mxpaths[cen].insert({diam(cen,chp_sub[cen][ord]),chp_sub[cen][ord]});
diams.insert({tdiam(cen),cen});
}
return diams.begin()->first;
}
void initialize(){
centroid_decomp(1);
}
int main(){
//freopen("ddiameter.in","r",stdin);
scanf("%d%d%lld",&N,&Q,&W);
for(int i=0;i<N-1;i++){
int a,b;
ll c;
scanf("%d%d%lld",&a,&b,&c);
edges.push_back({a,b});
adj[a].push_back(b);
adj[b].push_back(a);
w[{a,b}]=c;
w[{b,a}]=c;
}
initialize();
while(Q--){
ll d;ll e;
scanf("%lld%lld",&d,&e);
d=(d+last)%(N-1);
e=(e+last)%W;
last=query_cen(edges[d].first,edges[d].second,e);
printf("%lld\n",last);
}
}
Compilation message (stderr)
diameter.cpp: In function 'int main()':
diameter.cpp:198:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
198 | scanf("%d%d%lld",&N,&Q,&W);
| ~^ ~~
| | |
| int* ll* {aka long long int*}
| %lld
diameter.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
198 | scanf("%d%d%lld",&N,&Q,&W);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:202:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
202 | scanf("%d%d%lld",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | scanf("%lld%lld",&d,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |