This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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())
template<class T> using V = vector<T>;
using vi = V<int>;
const int nax = 6e4+5;
const int T = 21;
const int LG = 15;
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);
for(int i = LG - 1; i >= 0; i--) {
if (!(st[up[a][i]] <= st[b] && en[b] <= en[up[a][i]])) a = up[a][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;
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(prev(end(path)), begin(dpath), end(dpath));
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);
}
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, l, r; cin >> a >> b >> l >> r; --a, --b;
int p = lca(a, b);
int ans = 0;
for(int len = 1; len <= 20; len++) {
for(int rem = 0; rem < len; rem++) {
int L = (l - rem + len - 1) / len, R = (r - rem) / len;
int trafs = qry(rem, len, st[p], st[a]) + qry(rem, len, st[p], st[b]) - qry(rem, len, st[p], st[p]);
int times = R - L + 1;
ans += times * trafs;
// cout << rem << " " << len << endl;
// cout << a << " " << b << " | " << l << " " << r << " => " << trafs << " || " << L << " " << R << " => " << times << endl;
}
}
cout << ans << nl;
}
}
exit(0-0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |