#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, 0, -1, 0};
const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7;
const int mxn = 3e4 + 69, mxq = 1e5 + 5, sq = 500, mxv = 2e7 + 5;
//const int base = (1 <<18);
const int inf = 1e9 + 5, neg = -69420;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int x[9] = {0, 1, 1, -1, -1, 2, -2, 2, -2};
//const inty[9] = {0, 2, -2, 2, -2, 1, 1, -1, -1};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int n, k, q;
vt<int>adj[mxn + 1];
int tin[mxn + 1], tout[mxn + 1], dep[mxn + 1], up[mxn + 1][17], tt = 0;
struct BIT{
int bit[mxn + 1];
void upd(int p, int v){
while(p <= n){
bit[p] += v; p += p & (-p);
}
}
int get(int p){
int ans = 0;
while(p){
ans += bit[p]; p -= p & (-p);
}
return(ans);
}
};
BIT bit[21][21];
void dfs(int s, int pre){
tin[s] = ++tt;
for(auto v: adj[s]){
if(v != pre){
up[v][0] = s; dep[v] = dep[s] + 1;
dfs(v, s);
}
}
tout[s] = tt;
}
int lca(int u, int v){
if(dep[u] < dep[v])swap(u, v);
int k = dep[u] - dep[v];
forr(i, 0, 17){
if(k & (1 << i))u = up[u][i];
}
if(u == v)return(u);
dorr(i, 16, 0){
if(up[u][i] != up[v][i]){
u = up[u][i]; v = up[v][i];
}
}
return(up[u][0]);
}
void upd(int u, int v, int type){
int lc = lca(u, v);
vt<int>pathu, pathv;
int remu = u, remv = v;
while(u != lc){
pathu.pb(u); u = up[u][0];
}
while(v != lc){
pathv.pb(v); v = up[v][0];
}
pathu.pb(lc);
reverse(ALL(pathv));
for(auto i: pathv)pathu.pb(i);
int len = sz(pathu);
assert(len <= 20);
for(int i = 0; i < sz(pathu); i++){
//cout << pathu[i] << " " << tin[pathu[i]] << "\n";
bit[len][i].upd(tin[pathu[i]], 1 * type); bit[len][i].upd(tout[pathu[i]] + 1, -1 * type);
}
}
ll solve(int u, int v, ll t1,ll t2){
int lc = lca(u, v);
ll ans = 0;
for(int i = 1; i <= 20; i++){
for(int j = 0; j < i; j++){
ll cntver = bit[i][j].get(tin[u]) + bit[i][j].get(tin[v]) - bit[i][j].get(tin[lc]) - bit[i][j].get(tin[up[lc][0]]);
ll cnt = (t2 - j) / i + 1;
if(t1 - 1 - j >= 0){
cnt -= (t1 - 1 - j) / i + 1;
}
//cout << cnt << " ";
ans += cnt * cntver;
}
}
return(ans);
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("COLLEGE.INP", "r", stdin);
//freopen("COLLEGE.OUT", "w", stdout);
cin >> n;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
dfs(1, -1);
for(int i = 1; i < 16; i++){
for(int j = 1; j <= n; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
cin >> k;
for(int i = 0; i < k; i++){
int u, v; cin >> u >> v;
upd(u, v, 1);
}
cin >> q;
while(q--){
int idq; cin >> idq;
if(idq == 1){
int u, v; cin >> u >> v; upd(u, v, 1);
}else if(idq == 2){
int u, v; cin >> u >> v; upd(u, v, -1);
}else{
int u, v, t1, t2; cin >> u >> v >> t1 >> t2;
cout << solve(u, v, t1, t2) << "\n";
}
}
return(0);
}
/*
6 2
1 2
1 3
1 4
1 5
1 6
2 2
5 6
*/
Compilation message
traffickers.cpp: In function 'void upd(int, int, int)':
traffickers.cpp:80:9: warning: unused variable 'remu' [-Wunused-variable]
80 | int remu = u, remv = v;
| ^~~~
traffickers.cpp:80:19: warning: unused variable 'remv' [-Wunused-variable]
80 | int remu = u, remv = v;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
46328 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
50520 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
50524 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
51864 KB |
Output is correct |
| 2 |
Correct |
42 ms |
51548 KB |
Output is correct |
| 3 |
Correct |
36 ms |
52064 KB |
Output is correct |
| 4 |
Correct |
40 ms |
51960 KB |
Output is correct |
| 5 |
Correct |
41 ms |
51800 KB |
Output is correct |
| 6 |
Correct |
52 ms |
51896 KB |
Output is correct |
| 7 |
Correct |
36 ms |
51864 KB |
Output is correct |
| 8 |
Correct |
44 ms |
51804 KB |
Output is correct |
| 9 |
Correct |
32 ms |
52068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1016 ms |
55176 KB |
Output is correct |
| 2 |
Correct |
1060 ms |
55768 KB |
Output is correct |
| 3 |
Correct |
1083 ms |
55256 KB |
Output is correct |
| 4 |
Correct |
1040 ms |
54868 KB |
Output is correct |
| 5 |
Correct |
1059 ms |
54672 KB |
Output is correct |
| 6 |
Correct |
1034 ms |
55900 KB |
Output is correct |
| 7 |
Correct |
525 ms |
55956 KB |
Output is correct |
| 8 |
Correct |
455 ms |
55500 KB |
Output is correct |
