#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,k,q;
vector<int> G[30005];
int w[30005],Max[30005],lvl[30005],l[30005],poz[30005],t[30005],c[30005];
int cnt = 0, paths = 1;
void get_w(int nod, int dad = 0)
{
w[nod] = 1;
for(auto it : G[nod])
{
if(it==dad)
{
continue;
}
get_w(it,nod);
w[nod] += w[it];
t[it] = nod;
if(w[it] > w[Max[nod]])
{
Max[nod] = it;
}
}
}
void get_paths(int nod, int dad = 0, int level = 1)
{
lvl[nod] = level;
poz[nod] = (++cnt);
l[nod] = paths;
if(G[nod].size()==1 && nod!=1)
{
return;
}
get_paths(Max[nod],nod,level+1);
for(auto it : G[nod])
{
if(it==dad || it==Max[nod])
{
continue;
}
++paths;
c[paths] = it;
get_paths(it,nod,level+1);
}
}
int aib[25][25][300005];
int ub(int x)
{
return (x & (-x));
}
void update(int poz, int d, int r, int val)
{
for(int i=poz; i<=n; i+=ub(i))
{
if(r==0)
{
++aib[d][0][i];
continue;
}
for(int j=r; j<=d; j+=ub(j))
{
aib[d][j][i] += val;
}
}
}
int query(int tp, int poz)
{
int rez = 0;
for(int d=1; d<=20; d++)
{
for(int i=poz; i>=1; i-=ub(i))
{
int r = tp % d;
for(int j=r;j>=1;j-=ub(i))
{
rez += 1LL * aib[d][j][i] * (tp / d + 1);
}
rez += 1LL * aib[d][0][i] * (tp / d + 1);
for(int j=d;j>=1;j-=ub(j))
{
rez += 1LL * aib[d][j][i] * (tp / d);
}
for(int j=r;j>=1;j-=ub(j))
{
rez -= 1LL * aib[d][j][i] * (tp / d);
}
}
}
return rez;
}
void upd_traficker(int x, int y, int val)
{
vector<int> a,b;
while(x!=y)
{
if(lvl[x] > lvl[y])
{
a.push_back(x);
x = t[x];
}
else
{
b.push_back(y);
y = t[y];
}
}
a.push_back(x);
int nr = 0;
int dist = a.size() + b.size();
for(auto it : a)
{
update(poz[it],dist,nr,val);
++nr;
}
reverse(b.begin(),b.end());
for(auto it : b)
{
update(poz[it],dist,nr,val);
++nr;
}
}
int query_arb(int tp, int x, int y)
{
if(tp<0)
{
return 0;
}
int rez = 0;
while(l[x]!=l[y])
{
if(lvl[c[l[x]]] > lvl[c[l[y]]])
{
swap(x,y);
}
rez += query(tp,poz[y]) - query(tp,poz[c[l[y]]] - 1);
y = t[c[l[y]]];
}
if(poz[x] > poz[y])
{
swap(x,y);
}
rez += query(tp,poz[y]) - query(tp,poz[x]-1);
return rez;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1; i<n; i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
get_w(1);
lvl[1] = 1;
c[1] = 1;
get_paths(1);
cin>>k;
for(int i=1; i<=k; i++)
{
int x,y;
cin>>x>>y;
upd_traficker(x,y,+1);
}
cin>>q;
for(int i=1; i<=q; i++)
{
int tip;
cin>>tip;
if(tip==1)
{
int x,y;
cin>>x>>y;
upd_traficker(x,y,+1);
}
else if(tip==2)
{
int x,y;
cin>>x>>y;
upd_traficker(x,y,-1);
}
else
{
int x,y,t1,t2;
cin>>x>>y>>t1>>t2;
cout<<query_arb(t2,x,y) - query_arb(t1-1,x,y)<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
4564 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
4436 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
19584 KB |
Output isn't correct |
| 2 |
Incorrect |
137 ms |
17220 KB |
Output isn't correct |
| 3 |
Incorrect |
91 ms |
20572 KB |
Output isn't correct |
| 4 |
Incorrect |
130 ms |
19932 KB |
Output isn't correct |
| 5 |
Incorrect |
149 ms |
18652 KB |
Output isn't correct |
| 6 |
Incorrect |
154 ms |
19404 KB |
Output isn't correct |
| 7 |
Incorrect |
127 ms |
19744 KB |
Output isn't correct |
| 8 |
Incorrect |
115 ms |
21140 KB |
Output isn't correct |
| 9 |
Incorrect |
120 ms |
21464 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1741 ms |
53648 KB |
Output isn't correct |
| 2 |
Incorrect |
1386 ms |
57076 KB |
Output isn't correct |
| 3 |
Incorrect |
1273 ms |
57772 KB |
Output isn't correct |
| 4 |
Incorrect |
2059 ms |
51116 KB |
Output isn't correct |
| 5 |
Incorrect |
2354 ms |
53368 KB |
Output isn't correct |
| 6 |
Incorrect |
1157 ms |
57312 KB |
Output isn't correct |
| 7 |
Incorrect |
1167 ms |
59288 KB |
Output isn't correct |
| 8 |
Incorrect |
1228 ms |
58828 KB |
Output isn't correct |
