Submission #1322363

#TimeUsernameProblemLanguageResultExecution timeMemory
1322363behradSynchronization (JOI13_synchronization)C++20
100 / 100
180 ms21784 KiB
#ifdef LOCAL
#include "/home/bgopc/template/pch.hpp"
#endif
#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, m, q, in[maxn], out[maxn], T = 1, sz[maxn], ans[maxn], lst[maxn], up[maxn][LG], fen[maxn], active[maxn];
vector<int> g[maxn];
pii E[maxn];

void dfs(int v, int p = 0) {
  up[v][0] = p;
  for (int i = 1 ; i < LG ; i ++) up[v][i] = up[up[v][i - 1]][i - 1];

  in[v] = T ++;
  for (int u : g[v]) {
    if (u != p) dfs(u, v);
  }
  out[v] = T;
}

inline void add(int p, int x) {
  for (; p <= n + 1 ; p += p & -p) fen[p] += x;
}

inline int get(int p) {
  int res = 0;
  for (; p ; p -= p & -p) res += fen[p];
  return res;
}

inline int root(int v) {
  int u = v;
  for (int i = LG - 1 ; i >= 0 ; i --) {
    if (up[u][i] && get(in[up[u][i]]) == get(in[v])) u = up[u][i];
  }
  return u;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> m >> q;
  for (int i = 1 , u ,v ; i <= n - 1 ; i ++) {
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
    E[i] = {u, v};
  }

  dfs(1);

  for (int i = 1 ; i <= n ; i ++) ans[i] = 1;

  for (int i = 1 ; i <= n - 1 ; i ++) {
    auto &&[u, v] = E[i];
    if (v == up[u][0]) swap(u, v);
    add(in[v], 1);
    add(out[v], -1);
  }


  for (int e ; m -- ; ) {
    cin >> e;
    auto [u, v] = E[e];
    if (active[e]) {
      ans[v] = lst[v] = ans[root(u)];
      add(in[v], 1);
      add(out[v], -1);
    } else {
      ans[root(u)] += ans[v] - lst[v];
      add(in[v], -1);
      add(out[v], +1);
    }
    active[e] ^= 1;
  }

  for (int v ; q -- ; ) {
    cin >> v;
    cout << ans[root(v)] << nl;
  }
  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...