제출 #1339679

#제출 시각아이디문제언어결과실행 시간메모리
1339679Born_To_Laugh동기화 (JOI13_synchronization)C++17
100 / 100
174 ms32788 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 1e5 + 10;

int n, m, q;
vector<pair<int, int>> edges(maxn);
int cm[maxn];//cm[i] = so tt chung cua 2 dinh cua canh i
int cnt[maxn];//cnt[root]
vector<int> adj[maxn];

//HLD
int dep[maxn], big[maxn], sz[maxn];
int head[maxn], tin[maxn], binlift[maxn][20];
inline void pre_dfs(int a, int par){
    sz[a] = 1;
    cnt[a] = 1;
    for(auto &elm: adj[a]){
        if(elm == par)continue;
        dep[elm] = dep[a] + 1;
        
        binlift[elm][0] = a;
        for(int i=1; i<20; ++i) binlift[elm][i] = binlift[binlift[elm][i - 1]][i - 1];

        pre_dfs(elm, a);

        sz[a] += sz[elm];
        if(sz[elm] > sz[big[a]]) big[a] = elm;
    }
}
int id = 0;
inline void hld(int a, int par, int root){
    tin[a] = ++id;
    head[a] = root;

    if(big[a]) hld(big[a], a, root);

    for(auto &elm: adj[a]){
        if(elm == par || elm == big[a]) continue;
        hld(elm, a, elm);
    }
}

//fen
struct Fenwick
{
    int n;
    vector<int> bit;
    inline void init(int len){
        n = len;
        bit.assign(n + 1, 0);
    }
    inline void upd(int pos, int val){
        for(; pos<=n; pos += pos & -pos) bit[pos] += val;
    }
    inline int qr(int pos){
        int ans = 0;
        for(; pos>0; pos -= pos & -pos) ans += bit[pos];
        return ans;
    }
    inline int qr(int l, int r){
        return qr(r) - qr(l - 1);
    }
};

//solve
Fenwick ft;
int find_root(int a){
    while(1){
        if(ft.qr(tin[head[a]], tin[a]) != (tin[a] - tin[head[a]] + 1)){
            if(ft.qr(tin[a], tin[a]) != 1) return a;
            for(int i=19; i>=0; --i){
                int b = binlift[a][i];
                if(dep[b] >= dep[head[a]] &&
                    ft.qr(tin[b], tin[a]) == (tin[a] - tin[b] + 1)){
                    a = b;
                }
            }
            return binlift[a][0];
        }
        a = binlift[head[a]][0];
    }
}

void solve(){
    cin >> n >> m >> q;
    for(int i=1; i<n; ++i){
        int a, b;cin >> a >> b;
        edges[i] = {a, b};
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ft.init(n);

    dep[1] = 1;
    pre_dfs(1, -1);
    hld(1, -1, 1);

    while(m--){
        int x;cin >> x;
        int a = edges[x].fi, b = edges[x].se;
        if(dep[a] > dep[b]) swap(a, b);
        if(ft.qr(tin[b], tin[b]) == 1){
            int root = find_root(b);
            cnt[b] = cnt[root];
            cm[x] = cnt[root];
            ft.upd(tin[b], -1);
        }
        else{
            int root = find_root(a);
            cnt[root] += cnt[b] - cm[x];
            ft.upd(tin[b], 1);
        }
    }
    while(q--){
        int x;cin >> x;
        x = find_root(x);
        cout << cnt[x] << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#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...