제출 #1321209

#제출 시각아이디문제언어결과실행 시간메모리
1321209huoi동기화 (JOI13_synchronization)C++17
0 / 100
228 ms38832 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF

int n, m, q;
vector<pair<int, int>> edges;
vector<vector<int>> adj, up;
vector<int> depth, tin, tout, info, last, on;
int timer = 0;

struct FenwickTree {
    int n;
    vector<int> t;

    FenwickTree() {}
    FenwickTree(int n) : n(n), t(n) {}

    void init(int n_) {
        n = n_;
        t.resize(n_);
    }

    int lsb(int x) {
        return x & -x;
    }

    void update(int p, int x) {
        while (p <= n) {
            t[p] += x;
            p += lsb(p);
        }
    }

    int query(int p) {
        int ans = 0;
        while (p > 0) {
            ans += t[p];
            p -= lsb(p);
        }
        return ans;
    }
} ft;

void dfs(int u, int p = -1) {
    tin[u] = ++timer;
    for (int i = 0; i + 1 < 20; i++) {
        if (up[u][i] == -1) break;
        up[u][i + 1] = up[up[u][i]][i];
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
    tout[u] = timer;
}

int find_root(int u) {
    int root = u;
    for (int i = 19; i >= 0; i--) {
        if (up[root][i] == -1) continue;
        if (ft.query(tin[u]) == ft.query(tin[up[root][i]])) root = up[root][i];
    }
    return root;
}

void solve() {
    cin >> n >> m >> q;

    edges.resize(n);
    adj.resize(n + 1);
    up.resize(n + 1, vector<int>(20, -1));
    depth.resize(n + 1); tin.resize(n + 1); tout.resize(n + 1);
    info.resize(n + 1, 1); on.resize(n + 1); last.resize(n + 1);
    ft.init(n + 2);

    for (int i = 1; i < n; i++) {
        cin >> edges[i].first >> edges[i].second;
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }

    dfs(1);

    auto print_ft = [&]() {
        cout << "[FT]: ";
        for (int i = 1; i <= n; i++) {
            cout << ft.query(i) << " ";
        }
        cout << "\n";
    };

    auto print_roots = [&]() {
        cout << "[ROOTS]: ";
        for (int u = 1; u <= n; u++) {
            cout << find_root(u) << " ";
        }
        cout << "\n";
    };

    auto print_info = [&]() {
        cout << "[INFO]: ";
        for (int u = 1; u <= n; u++) {
            cout << info[find_root(u)] << " ";
        }
        cout << "\n";
    };

    for (int u = 1; u <= n; u++) {
        ft.update(tin[u], 1);
        ft.update(tout[u] + 1, -1);
    }

    while (m--) {
        int d;
        cin >> d;

        auto [u, v] = edges[d];
        if (depth[v] < depth[u]) swap(u, v);

        if (on[v]) {
            // cout << "[QRY] turning off " << u << " " << v << "\n";
            on[v] = 0;
            info[v] = last[v] = info[find_root(v)];
            ft.update(tin[v], 1);
            ft.update(tout[v] + 1, -1);
        } else {
            // cout << "[QRY] turning on " << u << " " << v << "\n";
            on[v] = 1;
            int new_info = info[u] + info[v] - last[v];
            ft.update(tin[v], -1);
            ft.update(tin[v] + 1, 1);
            info[find_root(v)] = new_info;
            info[u] = new_info;
        }

        // print_roots();
        // print_info();
        // cout << "\n";
    }

    while (q--) {
        int c;
        cin >> c;
        cout << info[find_root(c)] << "\n";
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...