#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 30303;
const int M = 101010;
struct SEG {
ll tree[N];
void update(int a, int b, ll v) {
++b;
for (; a < N; a += a & -a)
tree[a] += v;
for (; b < N; b += b & -b)
tree[b] -= v;
}
ll query(int a) {
ll res = 0;
for (; a; a -= a & -a)
res += tree[a];
return res;
}
} t[20][20];
int n, k, q, d[N], pp[20][N], dfn[N], out[N], z;
vector<int> g[N];
void dfs(int p, int v) {
dfn[v] = ++z;
for (int x : g[v]) {
if (p == x)
continue;
pp[0][x] = v;
d[x] = d[v] + 1;
dfs(v, x);
}
out[v] = z;
}
vector<int> path(int u, int v) {
vector<int> U, V;
while (d[v] > d[u]) {
V.push_back(v);
v = pp[0][v];
}
while (d[u] > d[v]) {
U.push_back(u);
u = pp[0][u];
}
while (u != v) {
U.push_back(u);
V.push_back(v);
u = pp[0][u]; v = pp[0][v];
}
U.push_back(u);
while (!V.empty()) {
U.push_back(V.back());
V.pop_back();
}
return U;
}
int lca(int u, int v) {
if (d[u] > d[v])
swap(u, v);
int D = d[v] - d[u];
for (int j = 0; j < 20; j++) {
if (D >> j & 1)
v = pp[j][v];
}
for (int j = 19; j >= 0; j--) {
if (pp[j][u] != pp[j][v]) {
u = pp[j][u];
v = pp[j][v];
}
}
return (u == v) ? u : pp[0][u];
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 1);
for (int j = 1; j < 20; j++)
for (int i = 1; i <= n; i++)
pp[j][i] = pp[j - 1][pp[j - 1][i]];
cin >> k;
for (int i = 0; i < k; i++) {
int u, v; cin >> u >> v;
auto S = path(u, v);
int sz = S.size();
for (int i = 0; i < sz; i++)
t[sz - 1][i].update(dfn[S[i]], out[S[i]], 1);
}
cin >> q;
for (int i = 0; i < q; i++) {
int T; cin >> T;
if (T == 1) {
int u, v; cin >> u >> v;
auto S = path(u, v);
int sz = S.size();
for (int i = 0; i < sz; i++)
t[sz - 1][i].update(dfn[S[i]], out[S[i]], 1);
}
if (T == 2) {
int u, v; cin >> u >> v;
auto S = path(u, v);
int sz = S.size();
for (int i = 0; i < sz; i++)
t[sz - 1][i].update(dfn[S[i]], out[S[i]], -1);
}
if (T == 3) {
int u, v, t1, t2; cin >> u >> v >> t1 >> t2;
int r = lca(u, v);
ll ans = 0;
vector<int> s{ u, v, r, pp[0][r] };
for (int i = 0; i < 20; i++) {
for (int j = 0; j <= i; j++) {
auto f = [&](int y) {
ll x = t[i][j].query(dfn[y]);
return (t2 + i + 1 - j) / (i + 1) * x - (t1 + i - j) / (i + 1) * x;
};
ans += f(u) + f(v) - f(r);
if (r != 1)
ans -= f(pp[0][r]);
}
}
cout << ans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7296 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
22100 KB |
Output is correct |
| 2 |
Correct |
119 ms |
20960 KB |
Output is correct |
| 3 |
Correct |
140 ms |
22236 KB |
Output is correct |
| 4 |
Correct |
117 ms |
22080 KB |
Output is correct |
| 5 |
Correct |
109 ms |
22112 KB |
Output is correct |
| 6 |
Correct |
113 ms |
22056 KB |
Output is correct |
| 7 |
Correct |
119 ms |
22004 KB |
Output is correct |
| 8 |
Correct |
107 ms |
22112 KB |
Output is correct |
| 9 |
Correct |
82 ms |
22256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1256 ms |
55732 KB |
Output is correct |
| 2 |
Correct |
1494 ms |
56432 KB |
Output is correct |
| 3 |
Correct |
1218 ms |
56320 KB |
Output is correct |
| 4 |
Correct |
1211 ms |
55544 KB |
Output is correct |
| 5 |
Correct |
1369 ms |
55380 KB |
Output is correct |
| 6 |
Correct |
1287 ms |
56372 KB |
Output is correct |
| 7 |
Correct |
998 ms |
56620 KB |
Output is correct |
| 8 |
Correct |
983 ms |
56264 KB |
Output is correct |
