#include <bits/stdc++.h>
using namespace std;
class SegTree
{
int *arb[21][21];
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);
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);
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++)
{
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 |
2 ms |
2892 KB |
Output is correct |
| 2 |
Correct |
37 ms |
6188 KB |
Output is correct |
| 3 |
Correct |
32 ms |
8908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
424 ms |
54616 KB |
Output is correct |
| 2 |
Correct |
404 ms |
60896 KB |
Output is correct |
| 3 |
Correct |
490 ms |
39836 KB |
Output is correct |
| 4 |
Correct |
432 ms |
59152 KB |
Output is correct |
| 5 |
Correct |
466 ms |
65488 KB |
Output is correct |
| 6 |
Correct |
543 ms |
62524 KB |
Output is correct |
| 7 |
Correct |
540 ms |
57296 KB |
Output is correct |
| 8 |
Correct |
435 ms |
40744 KB |
Output is correct |
| 9 |
Correct |
521 ms |
37620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3584 ms |
171580 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3600 ms |
138516 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3595 ms |
120324 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3601 ms |
203536 KB |
Time limit exceeded |
| 5 |
Correct |
3302 ms |
207100 KB |
Output is correct |
| 6 |
Execution timed out |
3586 ms |
126760 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3582 ms |
107496 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3560 ms |
108400 KB |
Time limit exceeded |
