Submission #1344562

#TimeUsernameProblemLanguageResultExecution timeMemory
1344562shirokitoSynchronization (JOI13_synchronization)C++20
100 / 100
169 ms26316 KiB
#include <bits/stdc++.h>
using namespace std;

#define UP1(i, n) for (int i = 0; i < (n); i++)
#define UP2(i, a, b) for (int i = (a); i <= (b); i++)
#define UP3(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define DN1(i, n) for (int i = (n) - 1; i >= 0; i--)
#define DN2(i, a, b) for (int i = (a); i >= (b); i--)
#define DN3(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define FOR_IMPL(_1, _2, _3, _4, NAME, ...) NAME
#define FOR_UP(...) FOR_IMPL(__VA_ARGS__, UP3, UP2, UP1) (__VA_ARGS__)
#define FOR_DN(...) FOR_IMPL(__VA_ARGS__, DN3, DN2, DN1) (__VA_ARGS__)

#define POPCOUNT(n) __builtin_popcountll(n)
#define CLZ(n) __builtin_clzll(n)
#define CTZ(n) __builtin_ctzll(n)
#define LOG(n) __lg(n)
#define BIT(n, i) (((n) >> (i)) & 1LL)
#define FLIP(n, i) ((n) ^ (1LL << (i)))
#define ON(n, i) ((n) | (1LL << (i)))
#define OFF(n, i) ((n) & ~(1LL << (i)))

#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()

#define fi first
#define se second

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

#if __cplusplus <= 201402L
template <typename T> T gcd(T a, T b) { 
    return __gcd(a, b); 
}
template <typename T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);  
}  

template <class T> void remove_duplicate(vector<T> &v) {
    sort(v.begin(), v.end()); 
    v.resize(unique(v.begin(), v.end()) - v.begin());
} 

template <class T> bool maximize(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T> bool minimize(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}  

const int N = 2e5 + 24, LG = 24;

int n, m, q; pii edge[N];
int used[N]; ll ans[N], rem[N];
int tin[N], tout[N], par[N][LG], tdfs, h[N];
vector<int> g[N];

struct FenwickTree {
    ll t[N];

    void update(int i, ll val) {
        for (; i <= n; i += i & (-i)) t[i] += val;
    }

    void update_range(int l, int r, ll val) {
        update(l, val); update(r + 1, -val);
    }

    ll get(int i) {
        ll res = 0; for (; i > 0; i -= i & (-i)) {
            res += t[i];
        }
        return res;
    }
} fen;

void dfs(int u, int pre) {
    tin[u] = ++tdfs;
    
    par[u][0] = pre; FOR_UP (i, 1, LG - 1) {
        par[u][i] = par[par[u][i - 1]][i - 1];
    }

    for (int v: g[u]) if (v != pre) {
        h[v] = h[u] + 1;
        dfs(v, u);
    }

    tout[u] = tdfs;
}

int getRoot(int u) {
    FOR_DN (i, LG - 1, 0) {
        int p = par[u][i];
        if (p > 0 && h[u] - h[p] == fen.get(tin[u]) - fen.get(tin[p])) {
            u = p;
        }
    }
    return u;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n >> m >> q;
    
    FOR_UP (i, 1, n - 1) {
        auto &[u, v] = edge[i];
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    FOR_UP (i, 1, n - 1) {
        auto &[u, v] = edge[i];
        if (tin[u] > tin[v]) swap(u, v);
    }

    FOR_UP (i, 1, n) ans[i] = 1;

    FOR_UP (i, m) {
        int pos; cin >> pos;
        auto [u, v] = edge[pos];
        int root = getRoot(u);

        if (!used[pos]) {
            ans[root] += ans[v] - rem[pos];
            fen.update_range(tin[v], tout[v], 1);
        }
        else {
            ans[v] = ans[root];
            rem[pos] = ans[root];
            fen.update_range(tin[v], tout[v], -1);
        }

        used[pos] ^= 1;
    }

    FOR_UP (i, q) {
        int u; cin >> u; 
        u = getRoot(u);
        cout << ans[u] << '\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...