// 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 = 3e4+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 - 1;
};
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]] + 1, -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);
}
// exit(0);
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 < min(r + 1, len + 0LL); rem++) {
// cout << r - rem << " " << (r - rem) / len << endl;
ll L = (l - rem + len - 1) / len, R = (r - rem) / len;
ll trafs = qry(rem, len, st[p], st[a]) + qry(rem, len, st[p], st[b]) - qry(rem, len, st[p], st[p]);
ll times = R - L + 1;
ans += times * 1LL * trafs;
// cout << rem << " " << len << " ======> ";
// cout << a << " " << b << " | " << l << " " << r << " => ";
// cout << trafs << " || " << L << " " << R << " => " << times << endl;
}
cout << ans << nl;
}
}
exit(0-0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
9 ms |
52316 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
52316 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
54288 KB |
Output isn't correct |
| 2 |
Incorrect |
56 ms |
54096 KB |
Output isn't correct |
| 3 |
Incorrect |
60 ms |
54616 KB |
Output isn't correct |
| 4 |
Incorrect |
53 ms |
54448 KB |
Output isn't correct |
| 5 |
Incorrect |
67 ms |
54108 KB |
Output isn't correct |
| 6 |
Incorrect |
51 ms |
54348 KB |
Output isn't correct |
| 7 |
Incorrect |
53 ms |
54320 KB |
Output isn't correct |
| 8 |
Incorrect |
50 ms |
54476 KB |
Output isn't correct |
| 9 |
Correct |
45 ms |
54608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1269 ms |
58720 KB |
Output isn't correct |
| 2 |
Incorrect |
1381 ms |
59804 KB |
Output isn't correct |
| 3 |
Incorrect |
1182 ms |
59220 KB |
Output isn't correct |
| 4 |
Incorrect |
1215 ms |
58008 KB |
Output isn't correct |
| 5 |
Incorrect |
1327 ms |
57860 KB |
Output isn't correct |
| 6 |
Incorrect |
1327 ms |
59576 KB |
Output isn't correct |
| 7 |
Correct |
592 ms |
59784 KB |
Output is correct |
| 8 |
Correct |
624 ms |
59612 KB |
Output is correct |
