fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 1;
  5.  
  6. int n, q;
  7. vector<int> adj[N];
  8.  
  9. int sz[N], dep[N], par[N], heavy[N];
  10. int head[N], rev[N], pos[N], curPos;
  11.  
  12. void dfs(int u, int parent) {
  13.    sz[u] = 1;
  14.    par[u] = parent;
  15.    for (int v : adj[u]) {
  16.       if (v == parent) continue;
  17.       dep[v] = dep[u] + 1;
  18.       dfs(v, u);
  19.       sz[u] += sz[v];
  20.       if (sz[v] > sz[heavy[u]]) heavy[u] = v;
  21.    }
  22. }
  23.  
  24. void decompose(int u, int h) {
  25.    head[u] = h;
  26.    pos[u] = ++curPos;
  27.    rev[curPos] = u;
  28.    if (heavy[u] != 0) decompose(heavy[u], h);
  29.    for (int v : adj[u]) {
  30.       if (v == par[u] || heavy[u] == v) continue;
  31.       decompose(v, v);
  32.    }
  33. }
  34.  
  35. int st[4 * N];
  36.  
  37. void update(int id, int l, int r, int pos) {
  38.    if (l == r) {
  39.       st[id] ^= 1;
  40.       return;
  41.    }
  42.    if (pos <= (l + r) / 2) update(id << 1, l, (l + r) / 2, pos);
  43.    else update(id << 1 | 1, (l + r) / 2 + 1, r, pos);
  44.    st[id] = st[id << 1] + st[id << 1 | 1];
  45. }
  46.  
  47. int walk(int id, int l, int r, int x, int y) {
  48.    if (r < x || y < l) return -1;
  49.    if (st[id] == 0) return -1;
  50.    if (l == r) return l;
  51.    int left = walk(id << 1, l, (l + r) / 2, x, y);
  52.    if (left != -1) return left;
  53.    return walk(id << 1 | 1, (l + r) / 2 + 1, r, x, y);
  54. }
  55.  
  56. int queryPath(int v) {
  57.    stack<pair<int,int>> st; 
  58.    while (dep[head[v]] > dep[1]) {
  59.       st.emplace(pos[head[v]], pos[v]);
  60.       v = par[head[v]];
  61.    }
  62.    st.emplace(1, pos[v]);
  63.    while (st.size()) {
  64.       auto [l, r] = st.top(); st.pop();
  65.       int res = walk(1, 1, n, l, r);
  66.       if (res != -1) return rev[res];
  67.    }
  68.    return -1;
  69. }
  70.  
  71. void solve() {
  72.    cin >> n >> q;
  73.    for (int i = 1; i < n; ++i) {
  74.       int u, v; cin >> u >> v;
  75.       adj[u].push_back(v);
  76.       adj[v].push_back(u);
  77.    }
  78.    dfs(1, 0);
  79.    decompose(1, 1);
  80.    while (q--) {
  81.       int t, u; cin >> t >> u;
  82.       if (t & 1) cout << queryPath(u) << '\n';
  83.       else update(1, 1, n, pos[u]);
  84.    }
  85. }
  86.  
  87. int main() {
  88.    ios_base::sync_with_stdio(false);
  89.    cin.tie(nullptr), cout.tie(nullptr);
  90.    solve();
  91.    return 0;
  92. }
Success #stdin #stdout 0.01s 12748KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AXR9nh
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!