Submission #1322347

#TimeUsernameProblemLanguageResultExecution timeMemory
1322347behradSynchronization (JOI13_synchronization)C++20
30 / 100
164 ms33952 KiB
#if !defined(EVAL) && !defined(ONLINE_JUDGE)
#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, big[maxn], sz[maxn], hd[maxn], h[maxn], par[maxn], ans[maxn], lst[maxn];
vector<int> g[maxn];
set<pii> have[maxn];
pii E[maxn];

void PreDfs(int v) {
  big[v] = -1;
  sz[v] = 1;
  // index loop to avoid aliasing/iterator issues
  for (int i = 0; i < (int)g[v].size(); ++i) {
    int u = g[v][i];
    // erase parent link from child's adjacency safely
    auto it = find(g[u].begin(), g[u].end(), v);
    if (it != g[u].end()) g[u].erase(it);

    par[u] = v;
    h[u] = h[v] + 1;
    PreDfs(u);

    sz[v] += sz[u];
    if (big[v] == -1 || sz[u] > sz[big[v]]) {
      big[v] = u;
      // move heavy child to front (safe swap via find)
      auto pos = find(g[v].begin(), g[v].end(), u);
      if (pos != g[v].begin()) swap(g[v][0], *pos);
    }
  }
}

void dfs(int v) {
  in[v] = T ++;
  for (int u : g[v]) {
    hd[u] = (u == big[v]) ? hd[v] : u;
    dfs(u);
  }
  out[v] = T;
}

inline bool upd(int e) {
  auto [uu, vv] = E[e];
  int head = hd[uu];
  auto pr = have[head].insert(pii(in[vv], vv));
  if (!pr.second) have[head].erase(pr.first);
  return !pr.second;
}

inline int root(int v) {
  int orig = v;
  while (1) {
    auto &st = have[hd[v]];
    if (!st.empty()) {
      // find the last marker with in <= in[orig]
      auto it = st.upper_bound(pii(in[orig], INT_MAX));
      if (it != st.begin()) {
        --it;
        return it->ss;
      }
    }
    if (hd[v] == 1) return 1;
    v = par[hd[v]];
  }
}

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};
  }

  PreDfs(1);
  hd[1] = 1;
  dfs(1);

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

  for (int i = 1 ; i <= n - 1 ; i ++) {
    if (h[E[i].ff] > h[E[i].ss]) swap(E[i].ff, E[i].ss);
    upd(i);
  }

  for (int iter = 0; iter < m; ++iter) {
    int e;
    cin >> e;
    auto [u, v] = E[e];
    int r = root(u);
    if (upd(e)) ans[r] += ans[v] - lst[v];
    else ans[v] = lst[v] = ans[r];
  }

  for (int iter = 0; iter < q; ++iter) {
    int v;
    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...