제출 #1332969

#제출 시각아이디문제언어결과실행 시간메모리
1332969wangzhiyi33동기화 (JOI13_synchronization)C++20
100 / 100
209 ms21752 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

const int maxn=1e5;
int n,m,qu;
vector<int>adj[maxn+2];

int sub[maxn+2],big[maxn+2];
void dfs(int cur,int par){
    sub[cur]=1;
    for(auto x : adj[cur]){
        if(x==par)continue;
        dfs(x,cur);
        if(sub[x]>sub[big[cur]]){
            big[cur]=x;
        }
    }
}

int in[maxn+2],cnt,dep[maxn+2],root[maxn+2],p[maxn+2];
int blk[maxn+2];
void dfs2(int cur,int par,int r){
    root[cur]=r;
    p[cur]=par;
    in[cur]=++cnt;
    blk[cnt]=cur; 
    dep[cur]=dep[par]+1;

    if(big[cur]){
        dfs2(big[cur],cur,r);
    }

    for(auto x : adj[cur]){
        if(x==par || x==big[cur])continue;
        dfs2(x,cur,x);
    }
}

int fen[maxn+2];
void update(int x,int val){
    for(int q=x;q<=maxn;q+=(q&(-q))){
        fen[q]+=val;
    }
}

int query(int x){
    int tot=0;
    for(int q=x;q>0; q-=(q&(-q))){
        tot+=fen[q];
    }
    return tot;
}

int sum(int l,int r){
    if(l>r)return 0;
    return query(r)-query(l-1);
}

int bin(int val){
    int i=0,tot=0;
    for(int q=19;q>=0;q--){
        i+=(1<<q);
        if(i<=maxn && tot+fen[i]<val){
            tot+=fen[i];
        }
        else{
            i-=(1<<q);
        }
    }
    return i+1;
}

int leng(int l,int r){
    return r-l+1;
}

int fin(int x){

    while(x>1){
        // if(query(in[prv])==0){
        //     x=prv; break;
        // }
        //cout<<in[x]<<" K "<<root[x]<<" "<<query(in[x]-1)<<endl;
        if(sum(in[root[x]],in[x])!=0){
            int mana=bin(query(in[x]));
            x=mana; break;
        }
        else{
            // prv=root[x];
            x=p[root[x]];
        }
    }
    return blk[x];
}

int a[maxn+2],b[maxn+2];

void add(int cur,int par){
    //cout<<cur<<" "<<par<<endl;
    update(in[cur],-1);
    int mana=fin(par);
    //cout<<mana<<" "<<b[cur]-a[cur]<<endl;
    b[mana]+=(b[cur]-a[cur]);
}

void rem(int cur,int par){
    update(in[cur],1);
    int mana=fin(par);
    a[cur]=b[cur]=b[mana];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>qu;
    ii edge[n];
    for(int q=1;q<n;q++){
        int u,v; cin>>u>>v;
        adj[u].pb(v); adj[v].pb(u);
        edge[q]={u,v};
    }
    dfs(1,0); dfs2(1,0,1);
    for(int q=1;q<=n;q++){
        update(q,1);
        b[q]=1;
        if(q<n && in[edge[q].fir]<in[edge[q].sec]){
            swap(edge[q].fir,edge[q].sec);
        }
    }

    bool oke[n+1]; memset(oke,false,sizeof oke);
    for(int q=1;q<=m;q++){
        int idx; cin>>idx;
        if(oke[idx]){
            oke[idx]=false;
            rem(edge[idx].fir,edge[idx].sec);
        }
        else{
            oke[idx]=true;
            add(edge[idx].fir,edge[idx].sec);
        }
       // cout<<query(2)<<"K"<<endl;
    }

    while(qu--){
        int cur; cin>>cur;
        int mana=fin(cur);
        //cout<<mana<<endl;
        cout<<b[mana]<<endl;
    }
}
#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...