제출 #1370531

#제출 시각아이디문제언어결과실행 시간메모리
1370531otariusTraffickers (RMI18_traffickers)C++20
100 / 100
502 ms63228 KiB
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

#define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 3 * 1e4 + 15;

struct fenwick {
    int fnw[maxN];
    void init() {
        for (int i = 0; i < maxN; i++) fnw[i] = 0;
    }

    void add(int x, int d) {
        for ( ; x < maxN; x += (x & -x)) fnw[x] += d;
    }

    int get(int x) {
        int ans = 0;
        for ( ; x; x -= (x & -x)) ans += fnw[x];
        return ans;
    }

    int query(int l, int r) {
        return get(r) - get(l - 1);
    }
} bit[21][21], cnt[21];

vector<int> g[maxN];
int n, k, q, par[maxN][20], in[maxN], out[maxN], dep[maxN], tim;
void dfs(int v, int p) {
    in[v] = ++tim; dep[v] = dep[p] + 1; par[v][0] = p;
    for (int u : g[v]) {
        if (u == p) continue;
        dfs(u, v);
    }

    out[v] = tim;
}
bool is_anc(int x, int y) {
    if (x == 0) return 1;
    return (in[x] <= in[y] && out[x] >= out[y]);
}
int lca(int x, int y) {
    if (is_anc(x, y)) return x;
    if (is_anc(y, x)) return y;
    for (int j = 19; j >= 0; j--)
        if (!is_anc(par[x][j], y)) x = par[x][j];
    return par[x][0];
}

void update(int x, int y, int p) {
    int lc = lca(x, y), d = dep[x] + dep[y] - dep[lc] - dep[par[lc][0]], cur = 0;
    while (x != par[lc][0]) {
        bit[d][cur].add(in[x], p); bit[d][cur].add(out[x] + 1, -p);
        cnt[d].add(in[x], p); cnt[d].add(out[x] + 1, -p); cur++; x = par[x][0];
    }

    cur = 1;
    while (y != lc) {
        bit[d][d - cur].add(in[y], p); bit[d][d - cur].add(out[y] + 1, -p);
        cnt[d].add(in[y], p); cnt[d].add(out[y] + 1, -p); cur++; y = par[y][0];
    }
}

int get1(int v, int t, int d) {
    int ans = (t / d) * cnt[d].get(in[v]);
    for (int i = 0; i <= t % d; i++)
        ans += bit[d][i].get(in[v]);
    return ans;
}
int get(int v, int t1, int t2) {
    int ans = 0;
    for (int i = 1; i <= 20; i++)
        ans += get1(v, t2, i) - get1(v, t1 - 1, i);
    return ans;
}
void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        g[x].pb(y); g[y].pb(x);
    }

    dfs(1, 0);
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    cin >> k;
    while (k--) {
        int x, y;
        cin >> x >> y;
        update(x, y, 1);
    }

    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y; update(x, y, 1);
        } else if (t == 2) {
            int x, y; cin >> x >> y; update(x, y, -1);
        } else {
            int x, y, t1, t2;
            cin >> x >> y >> t1 >> t2;
            int lc = lca(x, y);
            cout << get(x, t1, t2) + get(y, t1, t2) - get(lc, t1, t2) - get(par[lc][0], t1, t2) << '\n';
        }
    }
}
int32_t main() { 
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…