#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
template <class T> void chkmax(T &a, T &b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T &b) {a = std::min(a, b);};
template <class T> void chkmax(T &a, T b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T b) {a = std::min(a, b);};
typedef long long llong;
const int MAXN = 30000 + 10;
const int MAXLEN = 20 + 5;
const int MAXLOG = 16;
const int INF = 1e9;
int n, k, q;
struct Sparse
{
int par[MAXLOG][MAXN];
int dep[MAXN];
void build (int _par[], int _dep[])
{
for (int i = 1 ; i <= n ; ++i)
{
par[0][i] = _par[i];
dep[i] = _dep[i];
}
for (int lg = 1 ; (1 << lg) <= n ; ++lg)
{
for (int i = 1 ; i <= n ; ++i)
{
par[lg][i] = par[lg - 1][par[lg - 1][i]];
}
}
}
void equalize(int &u, int v)
{
for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
{
if (dep[par[lg][u]] >= dep[v])
{
u = par[lg][u];
}
}
}
int calcLCA(int u, int v)
{
if (u == v)
{
return u;
}
for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
{
if (par[lg][u] != par[lg][v])
{
u = par[lg][u];
v = par[lg][v];
}
}
return par[0][u];
}
int findLCA(int u, int v)
{
if (dep[u] < dep[v])
{
std::swap(u, v);
}
equalize(u, v);
return calcLCA(u, v);
}
};
Sparse sparse;
struct Fenwick
{
int tree[MAXN];
void update(int idx, int val)
{
for (; idx <= n ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int idx)
{
int res = 0;
for (; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
void rangeUpdate(int l, int r, int val)
{
update(l, val);
update(r + 1, -val);
}
};
Fenwick cnt[MAXLEN];
Fenwick rem[MAXLEN][MAXLEN];
std::vector <int> g[MAXN];
int in[MAXN], out[MAXN], timer;
int dep[MAXN];
int par[MAXN];
void dfs(int node, int p)
{
in[node] = ++timer;
dep[node] = dep[p] + 1;
par[node] = p;
for (const int &u : g[node])
{
if (u == p)
{
continue;
}
dfs(u, node);
}
out[node] = timer;
}
void addLine(int u, int a, int b)
{
cnt[a].rangeUpdate(in[u], out[u], 1);
for (int i = b ; i < a ; ++i)
{
rem[a][i].rangeUpdate(in[u], out[u], 1);
}
}
void remLine(int u, int a, int b)
{
cnt[a].rangeUpdate(in[u], out[u], -1);
for (int i = b ; i < a ; ++i)
{
rem[a][i].rangeUpdate(in[u], out[u], -1);
}
}
void add(int u, int v)
{
int lca = sparse.findLCA(u, v);
int len = dep[u] + dep[v] - 2 * dep[lca];
int timer = 0;
while (true)
{
addLine(u, len + 1, timer);
if (u == lca)
{
break;
}
u = par[u];
timer++;
}
timer = len;
while (v != lca)
{
addLine(v, len + 1, timer);
timer--;
v = par[v];
}
}
void remove(int u, int v)
{
int lca = sparse.findLCA(u, v);
int len = dep[u] + dep[v] - 2 * dep[lca];
int timer = 0;
while (true)
{
remLine(u, len + 1, timer);
if (u == lca)
{
break;
}
u = par[u];
timer++;
}
timer = len;
while (v != lca)
{
remLine(v, len + 1, timer);
timer--;
v = par[v];
}
}
llong calcFor(int u, int t)
{
llong res = 0;
for (int len = 1 ; len <= 21 ; ++len)
{
res += 1LL * cnt[len].query(in[u]) * (t / len);
res += rem[len][t % len].query(in[u]);
}
return res;
}
llong calcPath(int u, int v, int t)
{
if (t < 0) return 0;
int lca = sparse.findLCA(u, v);
return calcFor(u, t) + calcFor(v, t) - calcFor(lca, t) - calcFor(par[lca], t);
}
llong query(int u, int v, int l, int r)
{
return calcPath(u, v, r) - calcPath(u, v, l - 1);
}
void solve()
{
dfs(1, 0);
sparse.build(par, dep);
std::cin >> k;
for (int i = 1 ; i <= k ; ++i)
{
int u, v;
std::cin >> u >> v;
add(u, v);
}
std::cin >> q;
for (int i = 1 ; i <= q ; ++i)
{
int qType;
std::cin >> qType;
if (qType == 1)
{
int u, v;
std::cin >> u >> v;
add(u, v);
continue;
}
if (qType == 2)
{
int u, v;
std::cin >> u >> v;
remove(u, v);
continue;
}
int u, v, l, r;
std::cin >> u >> v >> l >> r;
std::cout << query(u, v, l, r) << '\n';
}
}
void input()
{
std::cin >> n;
for (int i = 1 ; i < n ; ++i)
{
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2216 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3160 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
38 ms |
11644 KB |
Output is correct |
| 3 |
Correct |
37 ms |
12376 KB |
Output is correct |
| 4 |
Correct |
39 ms |
12632 KB |
Output is correct |
| 5 |
Correct |
41 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
40 ms |
12828 KB |
Output is correct |
| 7 |
Correct |
39 ms |
13828 KB |
Output is correct |
| 8 |
Correct |
43 ms |
13988 KB |
Output is correct |
| 9 |
Correct |
36 ms |
14172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
662 ms |
36076 KB |
Output is correct |
| 2 |
Correct |
651 ms |
36220 KB |
Output is correct |
| 3 |
Correct |
605 ms |
35960 KB |
Output is correct |
| 4 |
Correct |
727 ms |
35404 KB |
Output is correct |
| 5 |
Correct |
837 ms |
35184 KB |
Output is correct |
| 6 |
Correct |
640 ms |
36444 KB |
Output is correct |
| 7 |
Correct |
454 ms |
36516 KB |
Output is correct |
| 8 |
Correct |
509 ms |
36180 KB |
Output is correct |
