Submission #1298138

#TimeUsernameProblemLanguageResultExecution timeMemory
1298138kiteyuSynchronization (JOI13_synchronization)C++20
0 / 100
8092 ms17664 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 1e5;

int n,m,q,timer = 0,par[N+5],sz[N+5],head[N+5],tin[N+5];
int info[N+5],last_info[N+5],lst[N+5];
vector<pair<int,int>>g[N+5];

void dfs(int x){
    sz[x] = 1;
    for(pair<int,int> i : g[x]) if(i.fi != par[x]){
        par[i.fi] = x;
        dfs(i.fi);
        sz[x] += sz[i.fi];
    }
}

void hld(int x,int idchain){
    head[x] = idchain;
    tin[x] = ++timer;
    int nxt = -1;
    for(pair<int,int> i : g[x]) {
        if(i.fi == par[x]) continue;
        if(nxt == -1) nxt = i.fi;
        else if(sz[nxt] < sz[i.fi]) nxt = i.fi;
    }
    if(nxt != -1){
        hld(nxt,idchain);
    }
    for(pair<int,int> i : g[x]) {
        if(i.fi == par[x]) continue;
        if(i.fi != nxt) {hld(i.fi,i.fi);}
    }
}

int bit[2*N+5];
bool light[2*N+5],state[N+5];
vector<pair<int,int>> edge;

void upd(int idx,int val){
    for(;idx <= timer ; idx += (idx & -idx)) bit[idx] += val;
}
void upd_lr(int l,int r,int val){
    upd(l,val);
    upd(r+1,-val);
}
int get(int idx){
    int res = 0;
    for(;idx > 0 ; idx -= (idx & -idx)) res += bit[idx];
    return res;
}


int getroot(int x){
    while(true){
        if(light[x]) {
            x = par[x];
        }
        else {
            int v = get(tin[x]);
            if(v == x) break;
            x = v;
        }
    }
    return x;
}



void connect(int x,int y){
//    cout << x << ' ' << y << ":\n";
    x = getroot(x);
//    cout << x << ',' << head[x] << ',' << head[y] << ',' << info[x] << ',' << info[y] << "\n";
    info[x] = info[x] + info[y] - last_info[y];

    if(head[x] != head[y]) light[y]=1;
    else{
//        cout << tin[y] << ',' << tin[lst[y]] << "!\n";
        upd_lr(tin[y],tin[lst[y]],-y+x);
        lst[x] = lst[y];
    }
//    cout << get(tin[y]) << "!\n";
}

void disconnect(int x,int y){
    x = getroot(x);
//    cout << x << '.' << y << ' ' << last_info[y] << ' ' << info[y] << ' ' << info[x] << '\n';
    last_info[y] = info[y] = info[x];



    if(head[x] != head[y]) {
        light[y] = 0;
    }
    else{
        upd_lr(tin[y],tin[lst[y]],-x+y);
        lst[x] = par[y];
    }
//    cout << lst[x] << '.' << get(tin[y]) << "!\n";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1,x,y; i < n ; ++i){
        cin >> x >> y;
        g[x].push_back({y,i});
        g[y].push_back({x,i});
        edge.push_back({x,y});
    }
    dfs(1);
    hld(1,1);
    for(int i = 1 ; i <= n ; ++i){
        info[i] = 1;
        lst[i] = i;
        upd_lr(tin[i],tin[i],i);
    }

//    cout << "still here ?\n";

    for(int i = 0 ; i < n-1 ; ++i)
        if(par[edge[i].fi] == edge[i].se)
         swap(edge[i].fi,edge[i].se);
    for(int i = 1,x; i <= m ; ++i){
        cin >> x;
        x--;
//        cout << x << ' ' << state[x] << "====\n";
        if(state[x] == 0) {
            connect(edge[x].fi,edge[x].se);
        }
        else{
            disconnect(edge[x].fi,edge[x].se);
        }
        state[x]^=1;
    }
    for(int i = 1,x; i <= q ; ++i){
        cin >> x;
        cout << info[getroot(x)] << '\n';
    }
    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...