#include <bits/stdc++.h>
using namespace std;
class SegTree
{
int *arb[21][22];
public:
void Initialize(int lung)
{
int i,j;
for (i=1; i<=20; i++)
{
for (j=0; j<=i; j++)
{
arb[i][j]= new int [(4*lung+1)];
for (int t=0; t<=4*lung; t++)
{
arb[i][j][t]=0;
}
}
}
}
void update(int st,int dr,int nod,int poz,int val,int i,int j)
{
if (st>dr)
{
return;
}
if (st==dr)
{
arb[i][j][nod]+=val;
return;
}
int mij=(st+dr)/2;
if (poz<=mij)
{
update(st,mij,2*nod,poz,val,i,j);
}
else
{
update(mij+1,dr,2*nod+1,poz,val,i,j);
}
arb[i][j][nod]=arb[i][j][2*nod]+arb[i][j][2*nod+1];
}
int query(int st,int dr,int nod,int ua,int ub,int i,int j)
{
if (ua<=st&&dr<=ub)
{
return arb[i][j][nod];
}
int mij=(st+dr)/2,sum=0;
if (ua<=mij)
{
sum=sum+query(st,mij,2*nod,ua,ub,i,j);
}
if (mij<ub)
{
sum=sum+query(mij+1,dr,2*nod+1,ua,ub,i,j);
}
return sum;
}
}*ceam;
int tata[100005],niv[100005],mar[100005],poz[100005],lung[100005],id[100005],prim[100005],max_fiu[100005];
vector <int> v[100005];
void dfs(int x,int t)
{
tata[x]=t;
mar[x]=1;
niv[x]=niv[t]+1;
for (int i=0; i<v[x].size(); i++)
{
int nod=v[x][i];
if (v[x][i]!=t)
{
dfs(v[x][i],x);
mar[x]+=mar[nod];
if (mar[nod]>mar[max_fiu[x]])
{
max_fiu[x]=nod;
}
}
}
}
int q;
void construieste(int x,int t)
{
++lung[q];
poz[x]=lung[q];
if (lung[q]==1)
{
prim[q]=x;
}
id[x]=q;
if (mar[x]==1)
{
return;
}
construieste(max_fiu[x],x);
for (int i=0; i<v[x].size(); i++)
{
if (v[x][i]!=tata[x]&&v[x][i]!=max_fiu[x])
{
q++;
construieste(v[x][i],x);
}
}
}
int rmq[100005][20],lg;
int lca(int x,int y)
{
if (niv[x]<niv[y])
{
return lca(y,x);
}
int dif=niv[x]-niv[y];
for (int i=0; i<=lg; i++)
{
if ((dif&(1<<i)))
{
x=rmq[x][i];
}
}
if (x!=y)
{
for (int i=lg; i>=0; i--)
{
if (rmq[x][i]!=rmq[y][i])
{
x=rmq[x][i];
y=rmq[y][i];
}
}
x=rmq[x][0];
}
return x;
}
void updatetrafic(int x,int y,int valoare)
{
int salut,lungime,nr;
salut=lca(x,y);
lungime=niv[x]+niv[y]-2*niv[salut]+1;
nr=0;
while (x!=tata[salut])
{
ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,nr);
ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,lungime);
nr++;
x=tata[x];
}
nr=lungime-1;
x=y;
while (x!=salut)
{
ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,nr);
ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,lungime);
nr--;
x=tata[x];
}
}
int min1(int x,int y)
{
if (x>y)
{
return y;
}
return x;
}
int max1(int x,int y)
{
if (x<y)
{
return y;
}
return x;
}
long long catesunt(int x,int y,int i,int j)
{
if (id[x]==id[y])
{
int st=min1(poz[x],poz[y]);
int dr=max1(poz[x],poz[y]);
return ceam[id[x]].query(1,lung[id[x]],1,st,dr,i,j);
}
if (niv[prim[id[x]]]>niv[prim[id[y]]])
{
swap(x,y);
}
return catesunt(y,prim[id[y]],i,j)+catesunt(tata[prim[id[y]]],x,i,j);
}
long long rasp(int x,int y,int timp)
{
int i,j;
long long suma=0,numar=0;
if (timp<0)
{
return 0;
}
for (i=1; i<=20; i++)
{
if (catesunt(x,y,i,i)!=0)
{
for (j=0; j<i; j++)
{
if (timp<j)
{
numar=0;
}
else
{
numar=(timp-j)/i+1;
}
suma=suma+(1LL*catesunt(x,y,i,j)*numar);
}
}
}
return suma;
}
int n,x,i,j,y,queryuri,tip,t1,t2;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n;
for (i=1; i<n; i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
q=1;
dfs(1,0);
for (i=1; i<=n; i++)
{
rmq[i][0]=tata[i];
}
lg=log2(n);
for (i=1; i<=lg; i++)
{
for (j=1; j<=n; j++)
{
rmq[j][i]=rmq[rmq[j][i-1]][i-1];
}
}
construieste(1,0);
ceam= new SegTree [(q+1)];
for (i=1; i<=q; i++)
{
ceam[i].Initialize(lung[i]);
}
int traficanti;
cin>>traficanti;
for (i=1; i<=traficanti; i++)
{
cin>>x>>y;
updatetrafic(x,y,1);
}
cin>>queryuri;
for (int t=1; t<=queryuri; t++)
{
cin>>tip;
if (tip==1)
{
cin>>x>>y;
updatetrafic(x,y,1);
}
else if (tip==2)
{
cin>>x>>y;
updatetrafic(x,y,-1);
}
else
{
cin>>x>>y>>t1>>t2;
cout<<rasp(x,y,t2)-rasp(x,y,t1-1)<<'\n';
}
}
return 0;
}
Compilation message
traffickers.cpp: In function 'void dfs(int, int)':
traffickers.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i=0; i<v[x].size(); i++)
| ~^~~~~~~~~~~~
traffickers.cpp: In function 'void construieste(int, int)':
traffickers.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i=0; i<v[x].size(); i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2892 KB |
Output is correct |
| 2 |
Correct |
37 ms |
6476 KB |
Output is correct |
| 3 |
Correct |
29 ms |
9500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
467 ms |
58984 KB |
Output is correct |
| 2 |
Correct |
443 ms |
65476 KB |
Output is correct |
| 3 |
Correct |
466 ms |
43076 KB |
Output is correct |
| 4 |
Correct |
454 ms |
63948 KB |
Output is correct |
| 5 |
Correct |
461 ms |
70724 KB |
Output is correct |
| 6 |
Correct |
465 ms |
67416 KB |
Output is correct |
| 7 |
Correct |
455 ms |
61896 KB |
Output is correct |
| 8 |
Correct |
517 ms |
44044 KB |
Output is correct |
| 9 |
Correct |
550 ms |
40648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3599 ms |
185696 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3606 ms |
150036 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3605 ms |
130596 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3576 ms |
220112 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3599 ms |
223660 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3597 ms |
137392 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3574 ms |
117116 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3604 ms |
117904 KB |
Time limit exceeded |
