#include <bits/stdc++.h>
#define ll long long
#define vec vector
#define pb push_back
const int nmax = 50005;
using namespace std;
int n, k, q;
vec < int > g[nmax];
int depth[nmax], tin[nmax], tout[nmax], par[nmax][21];
int timer;
void dfs(int nod , int p){
depth[nod] = depth[p] + 1;
par[nod][0] = p;
tin[nod] = ++timer;
for(int j : g[nod]){
if(j == p)continue;
dfs(j,nod);
}
tout[nod] = ++timer;
}
long long fw[2*nmax][23][23];
int lca(int x ,int y){
if(x == y)return x;
if(depth[x] < depth[y])swap(x,y);
if(tin[x] > tin[y] && tout[x] < tout[y])return y;
for(int i = 20 ; i >= 0 ; i--){
int nd = par[x][i];
if(tin[nd] < tin[y] && tout[nd] > tout[y])continue;
x = nd;
}
return par[x][0];
}
void update( int nod , int rest , int lenght , int val){
int x = tin[nod];
while(x <= timer){
fw[x][lenght][rest] += val;
x += x&-x;
}
x = tout[nod];
while(x <= timer){
fw[x][lenght][rest] -= val;
x += x&-x;
}
}
long long get( int nod1 , int nod2 , int lenght , int rest){
int l = lca(nod1,nod2);
int x = tin[nod2];
ll rs = 0;
while(x > 0){
rs += fw[x][lenght][rest];
x -= x&-x;
}
x = tin[nod1];
while(x > 0){
rs += fw[x][lenght][rest];
x -= x&-x;
}
x = tin[l];
while(x > 0){
rs -= fw[x][lenght][rest];
x -= x&-x;
}
x = tin[l] - 1;
while(x > 0){
rs -= fw[x][lenght][rest];
x -= x&-x;
}
return rs;
}
int main(){
cin >> n;
for(int i = 1 ; i < n ; i++){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1,0);
for(int j = 1; (1<<j) <= n; j++){
for(int i = 1 ; i <= n ; i++){
par[i][j] = par[par[i][j-1]][j-1];
}
}
tout[0] = timer + 1;
cin >> k;
for(int i = 1; i <= k; i++){
int a, b;
cin >> a >> b;
int l = lca(a,b);
int lenght = depth[a] + depth[b] - 2 * depth[l] + 1;
int nod = a, rest = 0;
while(nod != l){
update(nod,rest,lenght,1);
nod = par[nod][0];
++rest;
}
nod = b , rest = lenght - 1;
while(nod != l){
update(nod,rest,lenght,1);
nod = par[nod][0];
--rest;
}
update(nod,rest,lenght,1);
}
cin >> q;
for(int ii = 0 ; ii < q ; ii++){
int type, a, b;
cin >> type >> a >> b;
if(type == 1){
int l = lca(a,b);
int lenght = depth[a] + depth[b] - 2 * depth[l] + 1;
int nod = a, rest = 0;
while(nod != l){
update(nod,rest,lenght,1);
nod = par[nod][0];
++rest;
}
nod = b , rest = lenght - 1;
while(nod != l){
update(nod,rest,lenght,1);
nod = par[nod][0];
--rest;
}
update(nod,rest,lenght,1);
}
if(type == 2){
int l = lca(a,b);
int lenght = depth[a] + depth[b] - 2 * depth[l] + 1;
int nod = a, rest = 0;
while(nod != l){
update(nod,rest,lenght,-1);
nod = par[nod][0];
++rest;
}
nod = b , rest = lenght - 1;
while(nod != l){
update(nod,rest,lenght,-1);
nod = par[nod][0];
--rest;
}
update(nod,rest,lenght,-1);
}
if(type == 3){
long long t1 , t2;
cin >> t1 >> t2;
int l = lca(a,b);
if(tin[a] > tin[b])swap(a,b);
ll rez = 0;
t1--;
for(int i = 1; i <= 20 ; i++){
for(int j = 0 ; j < i ; j++){
ll gt = get(a,b,i,j);
if(gt != 0){
cout << a << ' ' << b << ' ' << i << ' ' << j << ' ' << gt << '\n';
}
rez += get(a,b,i,j)*(t2/i + (t2%i>=j ? 1 : 0) - t1/i - (t1%i>=j ? 1 : 0));
}
}
cout << rez << '\n';
}
}
}
Compilation message
traffickers.cpp: In function 'int main()':
traffickers.cpp:156:9: warning: unused variable 'l' [-Wunused-variable]
156 | int l = lca(a,b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2028 KB |
Output isn't correct |
| 2 |
Incorrect |
77 ms |
11116 KB |
Output isn't correct |
| 3 |
Incorrect |
69 ms |
10348 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
719 ms |
96492 KB |
Output isn't correct |
| 2 |
Incorrect |
762 ms |
86252 KB |
Output isn't correct |
| 3 |
Incorrect |
622 ms |
94956 KB |
Output isn't correct |
| 4 |
Incorrect |
696 ms |
95756 KB |
Output isn't correct |
| 5 |
Incorrect |
747 ms |
93380 KB |
Output isn't correct |
| 6 |
Incorrect |
741 ms |
94700 KB |
Output isn't correct |
| 7 |
Incorrect |
713 ms |
94444 KB |
Output isn't correct |
| 8 |
Incorrect |
679 ms |
98900 KB |
Output isn't correct |
| 9 |
Incorrect |
772 ms |
99820 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3587 ms |
326780 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3614 ms |
336620 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3577 ms |
329968 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3596 ms |
315544 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3552 ms |
307844 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3609 ms |
334608 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3602 ms |
323908 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3612 ms |
324608 KB |
Time limit exceeded |
