Submission #1344718

#TimeUsernameProblemLanguageResultExecution timeMemory
1344718WarinchaiSynchronization (JOI13_synchronization)C++20
100 / 100
198 ms20252 KiB
#include<bits/stdc++.h>
using namespace std;

vector<int>adj[100005];
int sz[100005],hv[100005],hd[100005],in[100005],out[100005],rv[100005],lv[100005],pa[100005],prv[100005],open[100005],val[100005];
vector<pair<int,int>>e;
int cur=0;
int n,m,q;

struct segtree{
    int info[400005];
    void build(int st,int en,int i){
        if(st==en)return info[i]=1,void();
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
    void upd(int st,int en,int i,int pos){
        if(st>pos||en<pos)return;
        if(st==en)return info[i]^=1,void();
        int m=(st+en)/2;
        upd(st,m,i*2,pos);
        upd(m+1,en,i*2+1,pos);
        info[i]=info[i*2]+info[i*2+1];
    }
    int fans(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
    }
    int f(int st,int en,int i,int l,int r){
        if(st>r||en<l||info[i]==0)return 0;
        if(st==en)return st;
        int m=(st+en)/2;
        int temp=f(m+1,en,i*2+1,l,r);
        if(temp)return temp;
        return f(st,m,i*2,l,r);
    }
}tr;

void dfs(int u,int p){
    sz[u]=1;
    for(auto x:adj[u])if(x!=p){
        dfs(x,u);
        sz[u]+=sz[x];
        if(sz[x]>sz[hv[u]])hv[u]=x;
    }
}

void efs(int u,int p,int r){
    pa[u]=p;
    lv[u]=lv[p]+1;
    in[u]=++cur;
    rv[cur]=u;
    hd[u]=r;
    if(hv[u])efs(hv[u],u,r);
    for(auto x:adj[u])if(x!=p&&x!=hv[u])efs(x,u,x);
    out[u]=cur;
}

int frt(int u){
    while(u!=0){
        int v=hd[u];
        int cnt=tr.fans(1,n,1,in[v],in[u]);
        if(cnt==0){
            u=pa[v];
        }else{
            u=rv[tr.f(1,n,1,in[v],in[u])];
            break;
        }
    }
    return u;
}

void toggle(int a){
    auto [u,v]=e[a-1];
    int ll=(lv[u]>lv[v]?u:v);
    u=frt(u);
    v=frt(v);
    int cval;
    if(open[a]){
        cval=val[u];
        tr.upd(1,n,1,in[ll]);
        val[ll]=cval;
    }else{
        cval=val[u]+val[v]-prv[a];
        val[u]=val[v]=cval;
        tr.upd(1,n,1,in[ll]);
    }
    prv[a]=cval;
    open[a]^=1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)val[i]=1;
    tr.build(1,n,1);
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        e.push_back({a,b});
    }
    dfs(1,0);
    efs(1,0,1);
    for(int i=0;i<m;i++){
        int x;cin>>x;
        toggle(x);
    }
    for(int i=0;i<q;i++){
        int x;cin>>x;
        int temp=frt(x);
        //cerr<<"qr:"<<x<<" "<<temp<<"\n";
        cout<<val[temp]<<"\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...