Submission #988818

#TimeUsernameProblemLanguageResultExecution timeMemory
988818LOLOLOTraffickers (RMI18_traffickers)C++17
100 / 100
1789 ms109648 KiB
#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...