Submission #1345734

#TimeUsernameProblemLanguageResultExecution timeMemory
1345734pcheloveksSynchronization (JOI13_synchronization)C++20
100 / 100
170 ms22136 KiB
#define _CRT_SECURE_NO_WARNINGS

/*
⣿⡟⡡⠾⠛⠻⢿⣿⣿⣿⡿⠃⣿⡿⣿⠿⠛⠉⠠⠴⢶⡜⣦⡀⡈⢿⣿
⡿⢀⣰⡏⣼⠋⠁⢲⡌⢤⣠⣾⣷⡄⢄⠠⡶⣾⡀⠀⣸⡷⢸⡷⢹⠈⣿
⡇⢘⢿⣇⢻⣤⣠⡼⢃⣤⣾⣿⣿⣿⢌⣷⣅⡘⠻⠿⢛⣡⣿⠀⣾⢠⣿
⣷⠸⣮⣿⣷⣨⣥⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢁⡼⠃⣼⣿
⡟⠛⠛⠛⣿⠛⠛⢻⡟⠛⠛⢿⡟⠛⠛⡿⢻⡿⠛⡛⢻⣿⠛⡟⠛⠛⢿
⡇⢸⣿⠀⣿⠀⠛⢻⡇⠸⠃⢸⡇⠛⢛⡇⠘⠃⢼⣷⡀⠃⣰⡇⠸⠇⢸
⡇⢸⣿⠀⣿⠀⠛⢻⡇⢰⣿⣿⡇⠛⠛⣇⢸⣧⠈⣟⠃⣠⣿⡇⢰⣾⣿
⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢋⣿⠙⣷⢸⣷⠀⣿⣿⣿
⣿⣿⣿⡇⢻⣿⣿⣿⡿⠿⢿⣿⣿⣿⠟⠋⣡⡈⠻⣇⢹⣿⣿⢠⣿⣿⣿
⣿⣿⣿⣿⠘⣿⣿⣿⣿⣯⣽⣉⣿⣟⣛⠷⠙⢿⣷⣌⠀⢿⡇⣼⣿⣿⣿
⣿⣿⣿⡿⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⡙⢿⢗⣀⣁⠈⢻⣿
*/

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

//Donald Trump pleese save this code
//Babahnineeleven will win IOI 2040
//Babahnineeleven will win IOI 2041
//Babahnineeleven will win IOI 2042
//Babahnineeleven will win IOI 2043
//Babahnineeleven will win IOI 2044
//Babahnineeleven will win IOI 2045
//Babahnineeleven will win IOI 2046
//Babahnineeleven will win IOI 2047
//Babahnineeleven will win IOI 2048
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Kholod will win ICPC WF 2026
//Andrew Pavlyk is best coder in Khmelnytski

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <bitset>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <deque>
#include <stack>

#define endl '\n'

using namespace std;

FILE* stream;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ld, ld > pdd;
const long long DIM = 1000007;
const ld eps = 1e-12;
const long long INF = 1e18;
const long long Bsize = 450;
const int mod = 998244353;
const long long NUMSZ = 500;

class fenwickTree {
public:

    void init(int sz) {
        this->sz = sz;
        T.resize(sz + 1);
    }

    void add(int pos, int val) {
        for (int i = pos; i <= sz; i += i & -i) T[i] += val;
    }

    int sumPref(int pos) {
        int res = 0;
        for (int i = pos; i > 0; i -= i & -i) res += T[i];
        return res;
    }
    int sum(int l, int r) {
        return sumPref(r) - (l != 1 ? sumPref(l - 1) : 0);
    }

private:

    int sz;
    vector < int > T;
}t;

int n, m, q, timer;
vector < vector < pii > > v;

vector < int > tin, tout, euler;
vector < vector < int > > j;

vector < int > a, c;
vector < int > epos;

void dfs(int val, int prev, int num) {
    tin[val] = ++timer;
    euler[timer] = val;

    if (num != -1) epos[num] = val;

    j[0][val] = prev;
    for (int p = 1; p < 20; p++) {
        j[p][val] = j[p - 1][j[p - 1][val]];
    }

    for (auto e : v[val]) {
        if (e.second == num) continue;
        dfs(e.first, val, e.second);
    }

    tout[val] = timer;
}

int sumOnRout(int v1, int v2) {
    return t.sumPref(tin[v1]) - t.sumPref(tin[v2]);
}

int getRoot(int val) {
    for (int p = 19; p >= 0; p--) {
        if (sumOnRout(val, j[p][val]) == 0) val = j[p][val];
    }
    return val;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef _DEBUG
    freopen_s(&stream, "input.txt", "r", stdin);
    freopen_s(&stream, "output.txt", "w", stdout);
#endif

    cin >> n >> m >> q;
    v.resize(n + 1);

    a.resize(n + 1);
    c.resize(n + 1);

    tin.resize(n + 1);
    tout.resize(n + 1);
    euler.resize(n + 1);

    epos.resize(n + 1);

    j.resize(20, vector < int >(n + 1));

    for (int i = 1; i <= n; i++) {
        a[i] = 1;
        c[i] = 0;
    }
    for (int i = 1; i < n; i++) {
        int v1, v2;
        cin >> v1 >> v2;

        v[v1].push_back({ v2, i });
        v[v2].push_back({ v1, i });
    }

    timer = 0;
    dfs(1, 1, -1);

    t.init(timer + 1);

    vector < int > type(n, 1);
    for (int i = 2; i <= n; i++) {
        t.add(tin[i], +1);
        t.add(tout[i] + 1, -1);
    }
    
    for (int i = 0; i < m; i++) {
        int e;
        cin >> e;

        if (type[e] == 1) {
            int v1 = epos[e];
            int v2 = getRoot(j[0][v1]);

            a[v2] = a[v1] + a[v2] - c[v1];

            t.add(tin[v1], -1);
            t.add(tout[v1] + 1, +1);
        }
        else {
            int v1 = epos[e];

            a[v1] = a[getRoot(v1)];
            c[v1] = a[v1];

            t.add(tin[v1], +1);
            t.add(tout[v1] + 1, -1);
        }
        type[e] ^= 1;
    }
    for (int i = 0; i < q; i++) {
        int val;
        cin >> val;
        
        cout << a[getRoot(val)] << endl;
    }

    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...