#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];
}
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(r, v);
ll ans = 0;
vector<int> s{ u, v, r, pp[0][r] };
for (int y : s) {
if (y == 0)
continue;
for (int i = 0; i < 20; i++) {
for (int j = 0; j <= i; j++) {
ll x = t[i][j].query(dfn[y]);
ans += (t2 + i + 1 - j) / (i + 1) * x;
ans -= (t1 + i - j) / (i + 1) * x;
}
}
}
cout << ans << '\n';
}
}
}
Compilation message
traffickers.cpp: In function 'int main()':
traffickers.cpp:121:24: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
121 | int r = lca(r, v);
| ~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
6740 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
6688 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
20392 KB |
Output isn't correct |
| 2 |
Incorrect |
82 ms |
19432 KB |
Output isn't correct |
| 3 |
Incorrect |
80 ms |
20648 KB |
Output isn't correct |
| 4 |
Incorrect |
89 ms |
20512 KB |
Output isn't correct |
| 5 |
Incorrect |
92 ms |
20404 KB |
Output isn't correct |
| 6 |
Incorrect |
100 ms |
20500 KB |
Output isn't correct |
| 7 |
Incorrect |
80 ms |
20380 KB |
Output isn't correct |
| 8 |
Incorrect |
75 ms |
20540 KB |
Output isn't correct |
| 9 |
Incorrect |
58 ms |
20672 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
920 ms |
53272 KB |
Output isn't correct |
| 2 |
Incorrect |
903 ms |
53904 KB |
Output isn't correct |
| 3 |
Incorrect |
1004 ms |
53412 KB |
Output isn't correct |
| 4 |
Incorrect |
1085 ms |
52776 KB |
Output isn't correct |
| 5 |
Incorrect |
988 ms |
52492 KB |
Output isn't correct |
| 6 |
Incorrect |
898 ms |
53888 KB |
Output isn't correct |
| 7 |
Incorrect |
785 ms |
54148 KB |
Output isn't correct |
| 8 |
Incorrect |
796 ms |
53764 KB |
Output isn't correct |
