#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 3e4 + 10;
struct fen{
vector <int> f;
int N;
void ass(int n) {
N = n;
f.assign(n + 1, 0);
}
void upd(int i, int x) {
for (; i <= N; i += i & (-i))
f[i] += x;
}
int get(int i) {
int s = 0;
for (; i; i -= i & (-i))
s += f[i];
return s;
}
} f[21][21];
vector <int> ed[N];
int in[N], ou[N], timer = 1, p[N][20], dep[N];
int cc[N][21][21];
void dfs(int u, int v) {
dep[u] = dep[v] + 1;
p[u][0] = v;
for (int j = 1; j < 20; j++) {
p[u][j] = p[p[u][j - 1]][j - 1];
}
in[u] = ++timer;
for (auto x : ed[u]) {
if (x == v)
continue;
dfs(x, u);
}
ou[u] = timer;
}
bool is(int a, int b) {
return in[a] <= in[b] && ou[a] >= in[b];
}
int lca(int a, int b) {
if (is(a, b))
return a;
if (is(b, a))
return b;
for (int j = 19; j >= 0; j--) {
if (is(p[a][j], b) == 0)
a = p[a][j];
}
return p[a][0];
}
void add(int u, int v, int c) {
int anc = lca(u, v);
int cnt = dep[u] + dep[v] - dep[anc] * 2 + 1;
int x = 0, y = 1;
while (u != p[anc][0]) {
f[cnt][x].upd(in[u], c);
f[cnt][x].upd(ou[u] + 1, -c);
cc[u][cnt][x] += c;
u = p[u][0];
x++;
}
while (v != anc) {
f[cnt][cnt - y].upd(in[v], c);
f[cnt][cnt - y].upd(ou[v] + 1, -c);
cc[v][cnt][cnt - y] += c;
v = p[v][0];
y++;
}
}
ll answer(int u, int v, ll t) {
if (t == -1)
return 0;
int anc = lca(u, v);
ll ans = 0;
for (int i = 1; i <= 20; i++) {
for (int j = 0; j <= min(t, (ll)20); j++) {
ll num = (f[i][j].get(in[u]) + f[i][j].get(in[v]) - f[i][j].get(in[anc]) * 2 + cc[anc][i][j]);
if (num) {
ans += (ll)((t - j) / i + 1) * num;
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ed[0].pb(1);
ed[1].pb(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
ed[a].pb(b);
ed[b].pb(a);
}
dfs(0, 0);
for (int i = 1; i <= 20; i++) {
for (int j = 0; j <= 20; j++) {
f[i][j].ass(timer);
}
}
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
add(a, b, 1);
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int t;
cin >> t;
if (t == 1) {
int a, b;
cin >> a >> b;
add(a, b, 1);
}
if (t == 2) {
int a, b;
cin >> a >> b;
add(a, b, -1);
}
if (t == 3) {
int a, b, t1, t2;
cin >> a >> b >> t1 >> t2;
cout << answer(a, b, t2) - answer(a, b, t1 - 1) << '\n';
}
}
return 0;
}
// (n + ) * n
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1372 KB |
Output is correct |
2 |
Correct |
4 ms |
5212 KB |
Output is correct |
3 |
Correct |
8 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
105 ms |
36068 KB |
Output is correct |
2 |
Correct |
107 ms |
32492 KB |
Output is correct |
3 |
Correct |
98 ms |
34908 KB |
Output is correct |
4 |
Correct |
98 ms |
36264 KB |
Output is correct |
5 |
Correct |
102 ms |
35920 KB |
Output is correct |
6 |
Correct |
107 ms |
35960 KB |
Output is correct |
7 |
Correct |
94 ms |
35708 KB |
Output is correct |
8 |
Correct |
97 ms |
36528 KB |
Output is correct |
9 |
Correct |
92 ms |
36696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1695 ms |
108920 KB |
Output is correct |
2 |
Correct |
1684 ms |
109500 KB |
Output is correct |
3 |
Correct |
1626 ms |
109256 KB |
Output is correct |
4 |
Correct |
1687 ms |
108860 KB |
Output is correct |
5 |
Correct |
1789 ms |
108352 KB |
Output is correct |
6 |
Correct |
1699 ms |
109396 KB |
Output is correct |
7 |
Correct |
1157 ms |
109648 KB |
Output is correct |
8 |
Correct |
1198 ms |
109396 KB |
Output is correct |