#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
pii G[100005];
ll n,q,w,weight[100005],root,nr[100005],niv[100005],timp,in[100005],out[100005],parent[100005],ans;
int lg[100005];
vector<pii> muchii[100005];
struct interv
{
ll root,st,dr;
};
vector<interv> where[100005];
multiset<ll> setik;
bool use[100005];
struct date
{
ll val,st,dr;
};
vector<date> arb[100005],linie[100005];
vector<ll> toprop[100005];
vector<ll> edge;
vector<ll> tree;
int nvm[100005];
void build(ll index,ll nod,ll st,ll dr)
{
if(st>dr)
return;
if(st==dr)
{
if(index==10)
{
ll x=linie[index][st].st;
ll y=linie[index][st].dr;
ll pp=linie[index][st].val;
ll z=x;
}
arb[index][nod].st=linie[index][st].st;
arb[index][nod].dr=linie[index][st].dr;
return;
}
int mij=(st+dr)/2;
build(index,nod*2,st,mij);
build(index,nod*2+1,mij+1,dr);
arb[index][nod].st=arb[index][nod*2].st;
arb[index][nod].dr=arb[index][nod*2].dr;
}
void prop(ll index,ll nod)
{
ll val=toprop[index][nod];
for(int i=nod*2;i<=nod*2+1;i++)
{
arb[index][i].val+=val;
toprop[index][i]+=val;
}
}
void update(ll index,ll nod,ll st,ll dr,ll a, ll b, ll val)
{
if(st!=dr)
prop(index,nod);
toprop[index][nod]=0;
if(st>=a&&dr<=b)
{
arb[index][nod].val+=val;
toprop[index][nod]+=val;
return;
}
int mij=(st+dr)/2;
if(a<=mij)
update(index,nod*2,st,mij,a,b,val);
if(b>mij)
update(index,nod*2+1,mij+1,dr,a,b,val);
arb[index][nod].val=max(arb[index][nod*2].val,arb[index][nod*2+1].val);
if(arb[index][nod].val==arb[index][nod*2].val)
{
arb[index][nod].st=arb[index][nod*2].st;
arb[index][nod].dr=arb[index][nod*2].dr;
}
else
{
arb[index][nod].st=arb[index][nod*2+1].st;
arb[index][nod].dr=arb[index][nod*2+1].dr;
}
}
date query(ll index,ll nod,ll st,ll dr,ll a,ll b)
{
if(a>b||st>dr)
return {0,0,0};
if(st!=dr)
prop(index,nod);
toprop[index][nod]=0;
if(st>=a&&dr<=b)
return arb[index][nod];
int mij=(st+dr)/2;
date x={0,0,0},y={0,0,0};
if(a<=mij)
x=query(index,nod*2,st,mij,a,b);
if(b>mij)
y=query(index,nod*2+1,mij+1,dr,a,b);
if(x.val>y.val)
return x;
else
return y;
}
void dfs(int nod,int par)
{
nr[nod]=1;
parent[nod]=par;
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i].first;
if(fiu!=par&&!use[fiu])
{
edge.push_back(muchii[nod][i].second);
dfs(fiu,nod);
nr[nod]+=nr[fiu];
}
}
}
void liniarize(int nod,int par,int root)
{
timp++;
in[nod]=timp;
if(nod!=root)
{
if(par==root)
nvm[nod]=nod;
else
nvm[nod]=nvm[par];
}
else
nvm[nod]=nod;
tree.push_back(nod);
if(nod==root)
niv[nod]=1;
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i].first;
if(!use[fiu]&&fiu!=par)
{
niv[fiu]=niv[nod]+1;
liniarize(fiu,nod,root);
}
}
out[nod]=timp;
}
int centroid(ll nod)
{
edge.clear();
dfs(nod,0);
ll sz=nr[nod];
if(sz==1)
return nod;
while(true)
{
bool ok=1;
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i].first;
if(fiu!=parent[nod]&&!use[fiu])
if(nr[fiu]>sz/2)
{
ok=0;
parent[nod]=fiu;
parent[fiu]=0;
nr[nod]-=nr[fiu];
nr[fiu]=sz;
nod=fiu;
break;
}
}
if(!ok)
continue;
else
break;
}
bool good=0;
if(nod==10LL)
good=1;
tree.clear();
timp=0;
liniarize(nod,0,nod);
linie[nod].resize(sz+1);
for(int i:tree)
{
int st=in[nvm[i]],dr=out[nvm[i]];
linie[nod][in[i]]={i,st,dr};
}
arb[nod].resize(5*sz+5);
toprop[nod].resize(5*sz+5);
use[nod]=1;
lg[nod]=sz;
for(int i=0;i<edge.size();i++)
{
interv x;
x.root=nod;
ll e=edge[i];
ll a=G[e].first,b=G[e].second;
if(niv[a]<niv[b])
swap(a,b);
x.st=in[a];
x.dr=out[a];
where[e].push_back(x);
}
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i].first;
if(!use[fiu])
centroid(fiu);
}
}
ll calcbest(ll i)
{
date x=query(i,1,1,lg[i],1,lg[i]);
ll suma=x.val;
date a1=query(i,1,1,lg[i],1,x.st-1);
date a2=query(i,1,1,lg[i],x.dr+1,lg[i]);
suma+=max(a1.val,a2.val);
return suma;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q>>w;
for(int i=1;i<n;i++)
{
ll a,b,c;
cin>>a>>b>>c;
muchii[a].push_back({b,i});
muchii[b].push_back({a,i});
weight[i]=c;
G[i]={a,b};
}
root=centroid(1);
for(int i=1;i<=n;i++)
{
bool vv=0;
if(i==10)
vv=1;
build(i,1,1,lg[i]);
}
for(int i=1;i<n;i++)
for(int j=0;j<where[i].size();j++)
{
ll st=where[i][j].st;
ll dr=where[i][j].dr;
ll index=where[i][j].root;
update(index,1,1,lg[index],st,dr,weight[i]);
/*if(index==10)
cout<<arb[index][1].st<<' '<<arb[index][1].dr<<'\n';*/
}
for(int i=1;i<=n;i++)
if(arb[i].size()>=2)
{
ll suma=calcbest(i);
setik.insert(suma);
}
ans=*prev(setik.end());
ll last=0;
while(q--)
{
ll d,e;
cin>>d>>e;
d=(d+last)%(n-1)+1;
e=(e+last)%w;
ll dif=e-weight[d];
weight[d]+=dif;
for(int j=0;j<where[d].size();j++)
{
ll st=where[d][j].st;
ll dr=where[d][j].dr;
ll index=where[d][j].root;
ll suma=calcbest(index);
setik.erase(setik.find(suma));
update(index,1,1,lg[index],st,dr,dif);
suma=calcbest(index);
setik.insert(suma);
}
ans=*prev(setik.end());
cout<<ans<<'\n';
last=ans;
}
return 0;
}
Compilation message
diameter.cpp: In function 'void build(ll, ll, ll, ll)':
diameter.cpp:36:16: warning: unused variable 'y' [-Wunused-variable]
36 | ll y=linie[index][st].dr;
| ^
diameter.cpp:37:16: warning: unused variable 'pp' [-Wunused-variable]
37 | ll pp=linie[index][st].val;
| ^~
diameter.cpp:38:16: warning: unused variable 'z' [-Wunused-variable]
38 | ll z=x;
| ^
diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void liniarize(int, int, int)':
diameter.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(ll)':
diameter.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
diameter.cpp:195:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for(int i=0;i<edge.size();i++)
| ~^~~~~~~~~~~~
diameter.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
diameter.cpp:179:10: warning: variable 'good' set but not used [-Wunused-but-set-variable]
179 | bool good=0;
| ^~~~
diameter.cpp: In function 'int main()':
diameter.cpp:240:14: warning: variable 'vv' set but not used [-Wunused-but-set-variable]
240 | bool vv=0;
| ^~
diameter.cpp:246:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
246 | for(int j=0;j<where[i].size();j++)
| ~^~~~~~~~~~~~~~~~
diameter.cpp:271:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
271 | for(int j=0;j<where[d].size();j++)
| ~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(ll)':
diameter.cpp:213:1: warning: control reaches end of non-void function [-Wreturn-type]
213 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
24372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
24372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
24332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
27992 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
371 ms |
234492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
24372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
