#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(){
freopen("new.inp","r",stdin);
freopen("new.out","w",stdout);
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);
cout<<nod<<' '<<rest<<' '<<lenght<<'\n';
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){
}
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:158:9: warning: unused variable 'l' [-Wunused-variable]
158 | int l = lca(a,b);
| ^
traffickers.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | freopen("new.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen("new.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
1364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
