#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <ctype.h>
#define p(x,y) pair<x, y>
#define pii pair<int, int>
#define v(x) vector<x>
#define q(x) queue<x>
#define pq(x) priority_queue<x>
#define uppq(x, comp) priority_queue<x, vector<x>, comp>
#define st(x) set<x>
#define m(x, y) map<x, y>
#define fi(s,e) for(int i=s;i<e;i++)
#define fj(s,e) for(int j=s;j<e;j++)
#define fk(s,e) for(int k=s;k<e;k++)
typedef long long int ll;
typedef unsigned long long int ull;
typedef __int128 ulll;
using namespace std;
int n,k,q;
int ordernum;
v(int) pushvec;
v(v(int)) vec;
int order[2][30010];
int par[30010][20];
ll ans[50010];
ll fen[50010][20][21];
v(p(pii, pii)) pushlot;
v(v(p(pii, pii))) add;
v(v(p(pii, pii))) ask;
void up(int now, int parent){
order[0][now]=ordernum++;
par[now][0]=parent;
fi(1,16) par[now][i] = par[par[now][i-1]][i-1];
int sz = vec[now].size();
fi(0,sz){
int next = vec[now][i];
if(next != parent) up(next, now);
}
order[1][now]=ordernum;
return;
}
int find(int a, int b){
if(order[0][a] <= order[0][b] && order[1][a] >= order[1][b]) return a;
if(order[0][a] >= order[0][b] && order[1][a] <= order[1][b]) return b;
for(int i = 15; i >= 0; i--){
int anc = par[a][i];
if(order[0][anc] <= order[0][b] && order[1][anc] >= order[1][b]) continue;
a = anc;
}
return par[a][0];
}
void make(int a, int b, int th, int pl){
v(int) forward,backward;
v(int) tot;
int lca = find(a,b);
while(1){
forward.push_back(a);
if(a==lca) break;
a=par[a][0];
}
while(1){
backward.push_back(b);
if(b==lca) break;
b=par[b][0];
}
int sza,szb,sz;
sza = forward.size();
szb = backward.size();
for(int i = szb-2; i >= 0; i--) forward.push_back(backward[i]);
sz = sza+szb-1;
fi(0,sz){
int now = forward[i];
add[now].push_back({{th, pl},{i, sz}});
}
return;
}
void change(int t, int diff, int th, int sz){
while(t <= q+1){
fen[t][th][sz]+=diff;
t+=(t&(-t));
}
return;
}
int find(int l, int r, int th, int sz){
int ret=0;
while(r>0){
ret += fen[r][th][sz];
r -= (r&(-r));
}
l--;
while(l>0){
ret -= fen[l][th][sz];
l -= (l&(-l));
}
return ret;
}
void spreadfind(int now, int parent){
int sz1, sz2, sz;
sz1 = add[now].size();
fi(0,sz1){
p(pii, pii) pic = add[now][i];
change(pic.first.first, pic.first.second, pic.second.first, pic.second.second);
}
sz2 = ask[now].size();
fi(0,sz2){
p(pii, pii) pic = ask[now][i];
int tim = min(19, pic.second.first);
fj(0,tim+1){
fk(1,21){
ans[pic.first.first] += 1ll*pic.first.second*find(1, pic.second.second, j, k)*((pic.second.first-j)/k+1);
}
}
}
sz = vec[now].size();
fi(0,sz){
int next = vec[now][i];
if(next != parent) spreadfind(next, now);
}
fi(0,sz1){
p(pii, pii) pic = add[now][i];
change(pic.first.first, -pic.first.second, pic.second.first, pic.second.second);
}
return;
}
int main(void){
scanf("%d",&n);
fi(0,n+1) vec.push_back(pushvec);
fi(0,n+1) add.push_back(pushlot);
fi(0,n+1) ask.push_back(pushlot);
fi(1,n){
int a,b;
scanf("%d%d",&a,&b);
vec[a].push_back(b);
vec[b].push_back(a);
}
up(1,1);
scanf("%d",&k);
fi(0,k){
int a,b;
scanf("%d%d",&a,&b);
make(a,b,1,1);
}
scanf("%d",&q);
int qcnt=0;
fi(2,q+2){
int t,a,b;
scanf("%d%d%d",&t,&a,&b);
if(t==1) make(a,b,i,1);
else if(t==2) make(a,b,i,-1);
else{
int t1,t2,lca;
scanf("%d%d",&t1,&t2);
lca = find(a,b);
if(t1){
ask[a].push_back({{qcnt,-1},{t1-1,i}});
ask[b].push_back({{qcnt,-1},{t1-1,i}});
ask[lca].push_back({{qcnt,1},{t1-1,i}});
if(lca!=1) ask[par[lca][0]].push_back({{qcnt,1},{t1-1,i}});
}
ask[a].push_back({{qcnt,1},{t2,i}});
ask[b].push_back({{qcnt,1},{t2,i}});
ask[lca].push_back({{qcnt,-1},{t2,i}});
if(lca!=1) ask[par[lca][0]].push_back({{qcnt,-1},{t2,i}});
qcnt++;
}
}
spreadfind(1,-1);
fi(0,qcnt) printf("%lld\n",ans[i]);
return 0;
}
Compilation message
traffickers.cpp: In function 'int main()':
traffickers.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
traffickers.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
traffickers.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | scanf("%d",&k);
| ~~~~~^~~~~~~~~
traffickers.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
traffickers.cpp:179:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
traffickers.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d%d%d",&t,&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~~
traffickers.cpp:188:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
188 | scanf("%d%d",&t1,&t2);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2004 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
16176 KB |
Output is correct |
| 2 |
Correct |
141 ms |
15612 KB |
Output is correct |
| 3 |
Correct |
146 ms |
16588 KB |
Output is correct |
| 4 |
Correct |
135 ms |
16500 KB |
Output is correct |
| 5 |
Correct |
136 ms |
16096 KB |
Output is correct |
| 6 |
Correct |
134 ms |
16336 KB |
Output is correct |
| 7 |
Correct |
140 ms |
16236 KB |
Output is correct |
| 8 |
Correct |
131 ms |
16388 KB |
Output is correct |
| 9 |
Correct |
111 ms |
16712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1493 ms |
143464 KB |
Output is correct |
| 2 |
Correct |
1505 ms |
144168 KB |
Output is correct |
| 3 |
Correct |
1396 ms |
143132 KB |
Output is correct |
| 4 |
Correct |
1401 ms |
142256 KB |
Output is correct |
| 5 |
Correct |
1526 ms |
141412 KB |
Output is correct |
| 6 |
Correct |
1494 ms |
143876 KB |
Output is correct |
| 7 |
Correct |
1332 ms |
144040 KB |
Output is correct |
| 8 |
Correct |
1285 ms |
144268 KB |
Output is correct |
