// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
const int nax = 6e4+5;
const int T = 21;
const int LG = 16;
int A[T][T][nax];
void upd(int i, int j, int p, int x) { for(++p; p <= nax; p += p & -p) A[i][j][p - 1] += x; }
int qry(int i, int j, int r) { int s = 0; for(; r; r -= r & -r) s += A[i][j][r - 1]; return s; }
int qry(int i, int j, int l, int r) { return qry(i, j, r + 1) - qry(i, j, l); }
int main() {
cin.tie(0)->sync_with_stdio(0);
memset(A, 0, sizeof A);
int N; cin >> N;
V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v; --u, --v;
adj[u].pb(v);
adj[v].pb(u);
}
vi st(N), en(N), dep(N); V<vi> up(N, vi(LG)); int tim = 0;
function<void(int, int)> gen = [&](int u, int p) {
// cout << u << " <-> " << p << endl;
st[u] = tim++; dep[u] = (u == p ? 0 : dep[p] + 1);
up[u][0] = p; for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];
for(auto& v : adj[u]) if (v != p) {
// cout << v << " " << u << endl;
gen(v, u);
}
en[u] = tim++;
};
gen(0, 0);
auto lca = [&](int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
for(int i = 0; i < LG; i++) if ((d >> i) & 1) a = up[a][i];
if (a == b) return a;
for(int i = LG - 1; i >= 0; i--) {
if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
}
return up[a][0];
};
auto traf = [&](int a, int b, int d = +1) {
// cout << a << " " << b << " =====> ";
int l = lca(a, b);
// cout << l << endl;
int len = dep[a] + dep[b] - 2 * dep[l];
vi path;
while(a != l) {
path.pb(a);
a = up[a][0];
}
path.pb(l);
vi dpath;
while(b != l) {
dpath.pb(b);
b = up[b][0];
}
reverse(begin(dpath), end(dpath));
path.insert(end(path), begin(dpath), end(dpath));
// assert(len + 1 == sz(path));
// assert(len + 1 <= 20);
for(int r = 0; r < sz(path); r++) {
upd(r, sz(path), st[path[r]], d);
upd(r, sz(path), en[path[r]], -d);
}
// for(auto& x : path) cout << x << " ";
// cout << endl;
};
int K; cin >> K;
for(int i = 0; i < K; i++) {
int a, b; cin >> a >> b; --a, --b;
traf(a, b);
}
auto inside = [&](int a, int b, int c) {
if (a > b) return false;
return a <= c && c <= b;
};
auto compute = [&](int rem, int mod, ll L, ll R) {
ll bl = L / mod, br = R / mod;
ll ans = 0;
if (bl == br) {
ans += inside(L % mod, R % mod, rem);
} else {
ans += br - bl - 1;
ans += inside(L % mod, mod - 1, rem);
ans += inside(0, R % mod, rem);
}
return ans;
};
int Q; cin >> Q;
for(int i = 0; i < Q; i++) {
int t; cin >> t;
if (t == 1) {
int a, b; cin >> a >> b; --a, --b;
traf(a, b);
} else if (t == 2) {
int a, b; cin >> a >> b; --a, --b;
traf(a, b, -1);
} else if (t == 3) {
int a, b; ll l, r; cin >> a >> b >> l >> r; --a, --b;
int p = lca(a, b);
ll ans = 0;
for(int len = 1; len <= 20; len++) for(int rem = 0; rem < len; rem++) {
// cout << r - rem << " " << (r - rem) / len << endl;
ll trafs = qry(rem, len, st[p], st[a]) + qry(rem, len, st[p], st[b]) - qry(rem, len, st[p], st[p]);
ans += compute(rem, len, l, r) * 1LL * trafs;
// cout << rem << " " << len << " ======> ";
// cout << a << " " << b << " | " << l << " " << r << " => ";
// cout << trafs << " || " << compute(rem, len, r + 1) << " " << compute(rem, len, l) << " " << times << endl;
}
cout << ans << nl;
}
}
exit(0-0);
}
Compilation message
traffickers.cpp: In lambda function:
traffickers.cpp:73:7: warning: unused variable 'len' [-Wunused-variable]
73 | int len = dep[a] + dep[b] - 2 * dep[l];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
103764 KB |
Output is correct |
| 2 |
Correct |
16 ms |
104028 KB |
Output is correct |
| 3 |
Correct |
17 ms |
104140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
106068 KB |
Output is correct |
| 2 |
Correct |
103 ms |
105752 KB |
Output is correct |
| 3 |
Correct |
69 ms |
106328 KB |
Output is correct |
| 4 |
Correct |
90 ms |
106072 KB |
Output is correct |
| 5 |
Correct |
100 ms |
105820 KB |
Output is correct |
| 6 |
Correct |
97 ms |
106072 KB |
Output is correct |
| 7 |
Correct |
93 ms |
106096 KB |
Output is correct |
| 8 |
Correct |
72 ms |
106072 KB |
Output is correct |
| 9 |
Correct |
61 ms |
106528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1481 ms |
110696 KB |
Output is correct |
| 2 |
Correct |
1474 ms |
111564 KB |
Output is correct |
| 3 |
Correct |
1380 ms |
111112 KB |
Output is correct |
| 4 |
Correct |
1503 ms |
109908 KB |
Output is correct |
| 5 |
Correct |
1586 ms |
109728 KB |
Output is correct |
| 6 |
Correct |
1336 ms |
111428 KB |
Output is correct |
| 7 |
Correct |
837 ms |
111924 KB |
Output is correct |
| 8 |
Correct |
675 ms |
111188 KB |
Output is correct |
