#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
inline long long maxll(long long a,long long b){return a>b?a:b;}
#include<stdio.h>
#include<stdlib.h>
#define N 100005
/* RNG */
unsigned X=12345; int rand_(){return(X*=3)>>1;}
/* SORT */
int(*compar)(int,int);
void sort(int*aa,int l,int r)
{
while(l<r)
{
int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)];
while(j<k)
switch (compar(aa[j], p))
{
case 0:
++j;
break;
case -1:
t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;
break;
case 1:
t=aa[--k],aa[k]=aa[j],aa[j]=t;
break;
}
sort(aa,l,i);
l=k;
}
}
int compar_1(int i,int j){return i<j?-1:i>j?1:0;}
/* TREAP MULTISET */
#define M 500000
long long _A[M];
int _B[M],_L[M],_R[M],_K[M],_talc,_trash[M],_to;
void _treap_print_(int v)
{
if(!v)return;
_treap_print_(_L[v]);
printf(" (%lld %d)",_A[v],_K[v]);
_treap_print_(_R[v]);
}
void _treap_print(int v)
{
return;
_treap_print_(v);
puts("");
}
int _treap_new(long long x)
{
int p=_to?_trash[--_to]:++_talc;
_A[p]=x;
_B[p]=rand_();
_L[p]=_R[p]=0;
_K[p]=1;
return p;
}
void _split(int v,int*l,int*r,long long k)
{
if(!v){*l=*r=0;return;}
if(_A[v]<=k)
_split(_R[v],&_R[v],r,k), *l=v;
else
_split(_L[v],l,&_L[v],k), *r=v;
}
void _merge(int*v,int l,int r)
{
if(!l||!r){*v=l^r;return;}
if(_B[l]<_B[r])
_merge(&_L[r],l,_L[r]), *v=r;
else
_merge(&_R[l],_R[l],r), *v=l;
}
void _insert(int*v,long long k)
{
//puts("INSERT");
int t1,t2,t3,t4,t5;
_split(*v,&t5,&t3,k);
_split(t5,&t1,&t2,k-1);
//puts("S1"); _treap_print(t1); _treap_print(t2); _treap_print(t3);
if(!t2) t2 = _treap_new(k);
else ++_K[t2];
//_treap_print(t1); _treap_print(t2); _treap_print(t3);
_merge(&t4,t1,t2);
_merge(v,t4,t3);
}
void _delete(int*v,long long k)
{
int t1,t2,t3;
_split(*v,&t2,&t3,k);
_split(t2,&t1,&t2,k-1);
if(!t2) ;
else
{
if(_K[t2] > 1)--_K[t2];
else _trash[_to++]=t2,t2=0;
}
_merge(&t2,t1,t2);
_merge(v,t2,t3);
}
long long _sum_high2(int*v)
{
if(!*v)return 0;
int u=*v;
long long apar=0;
while(_R[u])apar=_A[u],u=_R[u];
if(_K[u]>1)return 2*_A[u];
long long one=_A[u];
if(_L[u])
{
u=_L[u];
while(_R[u])u=_R[u];
return _A[u]+one;
}
return one+apar;
}
/* RANGE_ADDITION UPDATE, RANGE MAX QUERY SEGMENT TREE */
typedef struct
{
long long*t,*lz;
int ll,rr;
} S;
void S_init(S*s,int ll,int rr)
{
s->ll=ll;
s->rr=rr;
int n=rr-ll+1;
while(n&n-1)++n;
n=n<<1;
s->t=(long long*)calloc(n,sizeof*s->t);
s->lz=(long long*)calloc(n,sizeof*s->lz);
}
void _S_push(S*s,int v,int l,int r)
{
if(s->lz[v])
{
s->t[v] += s->lz[v];
if(l^r)
{
s->lz[2*v+1]+=s->lz[v];
s->lz[2*v+2]+=s->lz[v];
}
s->lz[v]=0;
}
}
void _S_add(S*s,int v,int l,int r,int x,int y,long long k)
{
_S_push(s,v,l,r);
if(r<x||y<l)return;
if(x<=l&&r<=y)
{
s->lz[v]=k;
_S_push(s,v,l,r);
return;
}
_S_add(s,2*v+1,l,(l+r)/2,x,y,k);
_S_add(s,2*v+2,(l+r)/2+1,r,x,y,k);
s->t[v]=maxll(s->t[2*v+1],s->t[2*v+2]);
}
void S_add(S*s,int x,int y,long long k) { _S_add(s,0,s->ll,s->rr,x,y,k); }
long long _S_qry(S*s,int v,int l,int r,int x,int y)
{
_S_push(s,v,l,r);
if(r<x||y<l)return -1;
if(x<=l&&r<=y)return s->t[v];
return maxll(_S_qry(s,2*v+1,l,(l+r)/2,x,y),_S_qry(s,2*v+2,(l+r)/2+1,r,x,y));
}
long long S_qry(S*s,int x,int y) { return _S_qry(s,0,s->ll,s->rr,x,y); }
int n, q;
long long W;
typedef struct { int v, l; long long w; } edge;
edge e[N<<1];
int eo,h[N];
void link(int u,int v,long long w)
{
++eo;
e[eo].v=v;e[eo].w=w;e[eo].l=h[u];h[u]=eo;
}
int sz[N],ded[N],cenpar[N],in[N],csz[N],*ccrd[N],clb[N],*tin[N],*tout[N],edge_appear[N];
int *children[N],co[N];
S seg[N];
int multiset[N];
int lb(int cen,int x)
{
int o,l=0,r=csz[cen]-1;
while(l<=r)
{
o=(l+r)/2;
if(ccrd[cen][o]>=x)r=o-1;
else l=o+1;
}
return r+1;
}
void dfs0(int u,int p)
{
sz[u]=1;
for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[v]) dfs0(v,u), sz[u]+=sz[v];
}
int cen(int u,int p,int tn)
{
for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[v]&&sz[v]*2>=tn) return cen(v,u,tn);
return u;
}
int dfs1(int u,int p)
{
int zz=1;
for(int j=h[u];j;j=e[j].l)if(e[j].v!=p&&!ded[e[j].v])zz+=dfs1(e[j].v,u);
return zz;
}
int dfs2_o=0;
void dfs2(int cen,int u,int p)
{
ccrd[cen][dfs2_o++]=u;
for(int j=h[u];j;j=e[j].l)if(e[j].v!=p&&!ded[e[j].v])dfs2(cen,e[j].v,u);
}
void dfs3(int cen,int u,int p)
{
clb[u]=lb(cen,u);
for(int j=h[u];j;j=e[j].l)if(e[j].v!=p&&!ded[e[j].v])dfs3(cen,e[j].v,u);
}
int dfs4_timer=0;
void dfs4(int cen,int u,int p)
{
tin[cen][clb[u]]=dfs4_timer++;
for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[e[j].v]){
edge_appear[(j+1)/2]=cen;
dfs4(cen,v,u);
}
tout[cen][clb[u]]=dfs4_timer-1;
}
void dfs5(int cen,int u,int p)
{
for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[e[j].v]){
//printf(" On cen %d and go %d [%d %d] adding %lld\n",cen,v,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
S_add(seg+cen,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
dfs5(cen,v,u);
}
}
long long deep(int cen,int lbch)
{
return S_qry(seg+cen,tin[cen][lbch],tout[cen][lbch]);
}
void dfsdebug(int cen,int u,int p)
{
//printf(" %d: %lld\n",u,deep(cen,lb(cen,u)));
for(int v,j=h[u];j;j=e[j].l)if((v=e[j].v)!=p&&!ded[e[j].v]){
//printf(" On cen %d and go %d [%d %d] adding %lld\n",cen,v,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
//S_add(seg+cen,tin[cen][clb[v]],tout[cen][clb[v]],e[j].w);
dfsdebug(cen,v,u);
}
}
int focused_centroid;
int compar_2(int i,int j)
{
int szi=tin[focused_centroid][i];
int szj=tin[focused_centroid][j];
return szi<szj?-1:szi>szj?1:0;
}
/* multiset storing answer for each centroid */
int diameter;
int decomp(int u)
{
dfs0(u,-1);
u=cen(u,-1,sz[u]);
focused_centroid = u;
ded[u]=1;
/* dfs sz */
csz[u]=dfs1(u,-1);
/* allocate memory for cordinate compression , then do it */
ccrd[u]=(int*)malloc(csz[u]*sizeof**ccrd);
dfs2_o=0; dfs2(u,u,-1);
compar=compar_1;sort(ccrd[u],0,csz[u]);
/* initialize segtree */
S_init(seg+u,0,csz[u]);
/* calculate clb[v] for all v in sub u */
dfs3(u,u,-1);
/* euler tour */
tin[u]=(int*)malloc(csz[u]*sizeof**tin);
tout[u]=(int*)malloc(csz[u]*sizeof**tout);
dfs4_timer=0;
dfs4(u,u,-1);
/* add initial edge weights */
dfs5(u,u,-1);
//dfsdebug(u,u,-1);
/* create multiset of centroid's children with D[v]+w[v] */
multiset[u]=0;
int oooo=0;
for(int j=h[u];j;j=e[j].l)if(!ded[e[j].v])
{
//printf(" ON %d: child %d with weight %lld + %lld\n",u,e[j].v,e[j].w,S_qry(seg+u,tin[u][clb[e[j].v]],tout[u][clb[e[j].v]]));
if(deep(u,clb[e[j].v])==3382)
{
//printf(" EEEEEEE: %d %d\n",u,e[j].v);
}
_insert(multiset+u,deep(u,clb[e[j].v]));
++co[u];
}
/* store childrens and sort them by discovery time */
children[u]=(int*)malloc(sizeof**children*co[u]);
for(int j=h[u];j;j=e[j].l)if(!ded[e[j].v])children[u][oooo]=clb[e[j].v],++oooo;
compar=compar_2;
sort(children[u],0,co[u]);
/* */
//printf(" Of %d : %lld\n",u,_sum_high2(multiset+u));
//_treap_print(multiset[u]);
//puts("EEE"); _treap_print(multiset[u]); printf(" : %lld\n",_sum_high2(multiset+u));
_insert(&diameter,_sum_high2(multiset+u));
//printf(" MS %d : ",u); _treap_print(multiset[u]); _treap_print(diameter);
/* decomp on children */
for(int v,j=h[u];j;j=e[j].l)if(!ded[v=e[j].v]){
int vcen = decomp(v);
in[(j+1)/2]=u;
cenpar[vcen]=u;
}
return u;
}
/* return the lowest node between 2 node connected by edge j; j in [1..n-1] */
int edge_lower(int cen,int j)
{
int u=e[j*2].v,v=e[j*2-1].v;
if(tin[cen][lb(cen,u)]>tin[cen][lb(cen,v)])return u;
return v;
}
/* return order of v - direct children of centroid such that node (lbu) is contained in subtree of v
* */
int children_containing(int cen,int lbu)
{
int o,l=0,r=co[cen]-1,z=-1;
while(l<=r)
{
o=(l+r)/2;
if(tin[cen][children[cen][o]]>tin[cen][lbu])r=o-1,z=children[cen][o];
else l=o+1;
}
return children[cen][l-1];
}
void update_edge(int j,long long nw)
{
long long old=e[j*2-1].w;
long long delta = nw - e[j*2-1].w;
int cen = edge_appear[j];
//printf(" DELTA: %lld\n",delta);
while(cen)
{
_delete(&diameter,_sum_high2(multiset+cen));
int lower=edge_lower(cen,j);
int lblower=lb(cen,lower);
int child=children_containing(cen,lblower);
//printf(" UPDATING FOR %d, lblower = %d EDGE IS IN CHILD %d\n",cen,lower,ccrd[cen][child]);
_delete(multiset+cen,deep(cen,child));
S_add(seg+cen,tin[cen][lblower],tout[cen][lblower],delta);
_insert(multiset+cen,deep(cen,child));
if (child==lblower)
{
_delete(multiset+cen,deep(cen,child));
S_add(seg+cen,tin[cen][lblower],tout[cen][lblower],delta);
//children_w[cen][childo]=nw;
_insert(multiset+cen,deep(cen,child));
}
else
{
}
_insert(&diameter,_sum_high2(multiset+cen));
//printf("UPDATED FOR %d, GOING TO %d\n",cen,cenpar[cen]);_treap_print(multiset[cen]);
cen=cenpar[cen];
}
e[j*2-1].w = e[j*2].w = nw;
}
long long last_ans=0;
#define ASSERT(x) if (!(x)) __builtin_trap()
void test()
{
int t1=_treap_new(2);
_insert(&t1,2);
_insert(&t1,1);
_insert(&t1,3);
_delete(&t1,1);
_delete(&t1,2);
_delete(&t1,3);
_insert(&t1,1);
ASSERT(_sum_high2(&t1)==3);
_delete(&t1,1);
ASSERT(_sum_high2(&t1)==2);
_delete(&t1,2);
ASSERT(_sum_high2(&t1)==0);
ASSERT(_A[t1]==0);
ASSERT(t1==0);
_insert(&t1,2);
_insert(&t1,3);
_insert(&t1,1);
ASSERT(_sum_high2(&t1)==5);
t1=0;
S s;
S_init(&s,0,3);
S_add(&s,1,1,1000);
ASSERT(S_qry(&s,1,1)==1000);
ASSERT(S_qry(&s,2,3)==0);
ASSERT(S_qry(&s,1,3)==1000);
S_add(&s,1,1,-1000);
ASSERT(S_qry(&s,1,1)==0);
ASSERT(S_qry(&s,1,3)==0);
fputs("DONE TESTING\n",stderr);
}
inline long long answer()
{
int uu=diameter;
while (_R[uu])uu=_R[uu];
return _A[uu];
}
int main()
{
//test();
scanf("%d%d%lld",&n,&q,&W);
for(long long u,v,w,i=1;i<n;++i)
scanf("%lld%lld%lld",&u,&v,&w),link(u,v,w),link(v,u,w);
decomp(1);
//printf("%lld\n",answer());
for(long long id,nw;q--;)
{
scanf("%lld%lld",&id,&nw);
id = (id + last_ans) % (n-1);
nw = (nw + last_ans) % W;
update_edge(id+1,nw);
int uu=diameter;
while (_R[uu])uu=_R[uu];
printf("%lld\n",last_ans=_A[uu]);
}
}
Compilation message
diameter.c: In function 'S_init':
diameter.c:150:14: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
150 | while(n&n-1)++n;
| ~^~
diameter.c: In function 'children_containing':
diameter.c:394:27: warning: variable 'z' set but not used [-Wunused-but-set-variable]
394 | int o,l=0,r=co[cen]-1,z=-1;
| ^
diameter.c: In function 'update_edge':
diameter.c:406:15: warning: unused variable 'old' [-Wunused-variable]
406 | long long old=e[j*2-1].w;
| ^~~
diameter.c: In function 'main':
diameter.c:505:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
505 | scanf("%d%d%lld",&n,&q,&W);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.c:507:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
507 | scanf("%lld%lld%lld",&u,&v,&w),link(u,v,w),link(v,u,w);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.c:514:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
514 | scanf("%lld%lld",&id,&nw);
| ^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3186 ms |
103532 KB |
Output is correct |
| 2 |
Incorrect |
3131 ms |
106368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
