제출 #1359508

#제출 시각아이디문제언어결과실행 시간메모리
1359508njoop동기화 (JOI13_synchronization)C++20
30 / 100
210 ms30692 KiB
#include <bits/stdc++.h>

using namespace std;

struct sgt {
    int n;
    vector<int> zpos;

    void init(int sz) {
        n = sz;
        zpos.assign(4*n+10, -1);
        build(0, n, 0);
    }

    void build(int l, int r, int node) {
        if(l == r) {
            zpos[node] = l;
            return;
        }
        int mid = (l+r)/2;
        build(l, mid, node*2+1);
        build(mid+1, r, node*2+2);
        zpos[node] = max(zpos[node*2+1], zpos[node*2+2]);
    }

    void update(int l, int r, int idx, int val, int node) {
        if(l == r) {
            zpos[node] = (val == 1 ? -1 : l);
            return;
        }
        int mid = (l+r)/2;
        if(idx <= mid) update(l, mid, idx, val, node*2+1);
        else update(mid+1, r, idx, val, node*2+2);
        zpos[node] = max(zpos[node*2+1], zpos[node*2+2]);
    }

    int query(int l, int r, int ql, int qr, int node) {
        if(l > qr || r < ql) return -1;
        if(l >= ql && r <= qr) return zpos[node];
        int mid = (l+r)/2;
        return max(query(l, mid, ql, qr, node*2+1), query(mid+1, r, ql, qr, node*2+2));
    }

    void upd(int idx, int val) {
        update(0, n, idx, val, 0);
    }

    int qry(int ql, int qr) {
        return query(0, n, ql, qr, 0);
    }
};

struct hld {
    int n, cpos;
    vector<vector<int>> g;
    vector<int> sz, h, d, pos, rpos, pa, info, last;
    sgt seg;

    void init(int siz, const vector<vector<int>>& gr) {
        n = siz;
        g = gr;
        cpos = 0;
        sz.assign(n+2, 0);
        d.assign(n+2, 0);
        h.assign(n+2, 0);
        pos.assign(n+2, 0);
        rpos.assign(n+2, 0);
        pa.assign(n+2, 0);
        info.assign(n+2, 1);
        last.assign(n+2, 0);
        dfs_sz(1, -1, 0);
        dfs_h(1, -1, 1);
        for(int i=1; i<=n; i++) {
            rpos[pos[i]] = i;
        }
        seg.init(n);
    }

    void dfs_sz(int no, int rt, int dis) {
        sz[no]++;
        d[no] = dis;
        pa[no] = rt;
        for(auto i: g[no]) {
            if(i == rt) continue;
            dfs_sz(i, no, dis+1);
            sz[no] += sz[i];
        }
    }

    void dfs_h(int no, int rt, int hn) {
        int big = -1, cnt = 0;
        h[no] = hn;
        pos[no] = cpos;
        cpos++;
        for(auto i: g[no]) {
            if(i == rt) continue;
            if(sz[i] > cnt) {
                cnt = sz[i];
                big = i;
            }
        }
        if(big != -1) dfs_h(big, no, hn);
        for(auto i: g[no]) {
            if(i == rt || i == big) continue;
            dfs_h(i, no, i);
        }
    }

    int fr(int u) {
        int ans = u;
        while(u != 1) {
            int res = seg.qry(pos[h[u]], pos[u]);
            if(res != -1) {
                return rpos[res];
            }
            ans = h[u];
            u = pa[h[u]];
        }
        return ans;
    }

    void toggle(int u, int v) {
        if(d[u] > d[v]) swap(u, v);
        if(seg.qry(pos[v], pos[v]) == -1) {
            dc(v);
            seg.upd(pos[v], 0);
        } else {
            con(v);
            seg.upd(pos[v], 1);
        }
    }

    void con(int v) {
        int u = fr(pa[v]);
        info[u] += info[v] - last[v];
        last[v] = info[v];
    }

    void dc(int v) {
        int u = fr(pa[v]);
        info[v] = info[u];
        last[v] = info[u];
    }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> g(n+2, vector<int>());
    vector<pair<int, int>> edge(n+2, {0, 0});
    for(int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge[i] = {u, v};
    }
    hld tree;
    tree.init(n, g);
    while(m--) {
        int idx;
        cin >> idx;
        tree.toggle(edge[idx].first, edge[idx].second);
    }
    while(q--) {
        int idx;
        cin >> idx;
        cout << tree.info[tree.fr(idx)] << "\n";
    }
}
#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...