제출 #1321192

#제출 시각아이디문제언어결과실행 시간메모리
1321192huoi동기화 (JOI13_synchronization)C++17
10 / 100
8093 ms39012 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 kpar(int u, int k) {
    for (int i = 0; i < 20; i++) {
        if (u == -1) break;
        if (k & (1 << i)) u = up[u][i];
    }
    return u;
}

bool is_ancestor(int u, int v) {
    // returns true if u is ancestor of v
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

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);

    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;
            last[v] = info[v];
        } else {
            // cout << "[QRY] turning on " << u << " " << v << "\n";
            on[v] = 1;
            int new_info = info[u] + info[v] - last[v];

            queue<pair<int, int>> q;
            q.push({u, v});
            q.push({v, u});
            while (q.size()) {
                auto [x, p] = q.front();
                q.pop();
                info[x] = new_info;
                for (int y : adj[x]) {
                    if (y == p) continue;
                    int status = on[depth[x] > depth[y] ? x : y];
                    if (status == 1) {
                        q.push({y, x});
                    }
                }
            }
        }
    }

    while (q--) {
        int c;
        cin >> c;
        cout << info[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...