Submission #899787

#TimeUsernameProblemLanguageResultExecution timeMemory
899787CookieTraffickers (RMI18_traffickers)C++14
0 / 100
1125 ms55896 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359; using u128 = __uint128_t; const int x[4] = {1, 0, -1, 0}; const int y[4] = {0, -1, 0, 1}; const ll mod = 1e9 + 7; const int mxn = 3e4 + 69, mxq = 1e5 + 5, sq = 500, mxv = 2e7 + 5; //const int base = (1 <<18); const int inf = 1e9 + 5, neg = -69420; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); //const int x[9] = {0, 1, 1, -1, -1, 2, -2, 2, -2}; //const inty[9] = {0, 2, -2, 2, -2, 1, 1, -1, -1}; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> int n, k, q; vt<int>adj[mxn + 1]; int tin[mxn + 1], tout[mxn + 1], dep[mxn + 1], up[mxn + 1][17], tt = 0; struct BIT{ int bit[mxn + 1]; void upd(int p, int v){ while(p <= n){ bit[p] += v; p += p & (-p); } } int get(int p){ int ans = 0; while(p){ ans += bit[p]; p -= p & (-p); } return(ans); } }; BIT bit[21][21]; void dfs(int s, int pre){ tin[s] = ++tt; for(auto v: adj[s]){ if(v != pre){ up[v][0] = s; dep[v] = dep[s] + 1; dfs(v, s); } } tout[s] = tt; } int lca(int u, int v){ if(dep[u] < dep[v])swap(u, v); int k = dep[u] - dep[v]; forr(i, 0, 17){ if(k & (1 << i))u = up[u][i]; } if(u == v)return(u); dorr(i, 16, 0){ if(up[u][i] != up[v][i]){ u = up[u][i]; v = up[v][i]; } } return(up[u][0]); } void upd(int u, int v, bool type){ int lc = lca(u, v); vt<int>pathu, pathv; while(u != lc){ pathu.pb(u); u = up[u][0]; } while(v != lc){ pathv.pb(v); v = up[v][0]; } pathu.pb(lc); reverse(ALL(pathv)); for(auto i: pathv)pathu.pb(i); int len = sz(pathu); for(int i = 0; i < sz(pathu); i++){ //cout << pathu[i] << " " << tin[pathu[i]] << "\n"; bit[len][i].upd(tin[pathu[i]], 1 * type); bit[len][i].upd(tout[pathu[i]] + 1, -1 * type); } } ll solve(int u, int v, ll t1,ll t2){ int lc = lca(u, v); ll ans = 0; for(int i = 1; i <= 20; i++){ for(int j = 0; j < i; j++){ ll cntver = bit[i][j].get(tin[u]) + bit[i][j].get(tin[v]) - bit[i][j].get(tin[lc]) - bit[i][j].get(tin[up[lc][0]]); ll cnt = (t2 - j) / i + 1; if(t1 - 1 - j >= 0){ cnt -= (t1 - 1 - j) / i + 1; } //cout << cnt << " "; ans += cnt * cntver; } } return(ans); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("COLLEGE.INP", "r", stdin); //freopen("COLLEGE.OUT", "w", stdout); cin >> n; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1, -1); for(int i = 1; i < 16; i++){ for(int j = 1; j <= n; j++){ up[j][i] = up[up[j][i - 1]][i - 1]; } } cin >> k; for(int i = 0; i < k; i++){ int u, v; cin >> u >> v; upd(u, v, 1); } cin >> q; while(q--){ int idq; cin >> idq; if(idq == 1){ int u, v; cin >> u >> v; upd(u, v, 1); }else if(idq == 2){ int u, v; cin >> u >> v; upd(u, v, -1); }else{ int u, v, t1, t2; cin >> u >> v >> t1 >> t2; cout << solve(u, v, t1, t2) << "\n"; } } return(0); } /* 6 2 1 2 1 3 1 4 1 5 1 6 2 2 5 6 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...