Advertisement
midnight_sun

Untitled

Nov 15th, 2022
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
  3. #define a first
  4. #define b second
  5. using namespace std;
  6. const int MAXN = 2 * 1e6 + 1;
  7. typedef pair<pair<int, int>, pair<int, int>> pai;
  8. int n, q, parent[MAXN], fparent[MAXN], lvl[MAXN];
  9. vector<pai> v;
  10. stack<string> st;
  11. int find(int u) {
  12.     if (u == parent[u]) return u;
  13.     return parent[u] = find(parent[u]);
  14. }
  15. void merge(int u, int v) {
  16.     u = find(u);
  17.     v = find(v);
  18.     if (u == v) return;
  19.     if (lvl[u] > lvl[v]) swap(u, v);
  20.     parent[u] = v;
  21.     lvl[v] += lvl[u];
  22. }
  23. int main() {
  24.     fastio;
  25.     cin >> n >> q;
  26.     for (int i = 1; i <= n; i++) {
  27.         parent[i] = i;
  28.         lvl[i] = 1;
  29.     }
  30.     for (int i = 2; i <= n; i++) cin >> fparent[i];
  31.     fparent[1] = 1;
  32.     for (int x, a, b, i = 0; i < n - 1 + q; i++) {
  33.         cin >> x;
  34.         if (!x) {
  35.             cin >> a;
  36.             v.push_back({ {x,a},{0,0} });
  37.         }
  38.         else {
  39.             cin >> a >> b;
  40.             v.push_back({ {x,0},{a,b} });
  41.         }
  42.     }
  43.     std::reverse(v.begin(), v.end());
  44.     for (int i = 0; i < v.size(); i++) {
  45.         int x = v[i].a.a;
  46.         if (x == 0) {
  47.             int k = v[i].a.b;
  48.             merge(k, fparent[k]);
  49.         }
  50.         else {
  51.             int k1 = find(v[i].b.a), k2 = find(v[i].b.b);
  52.             if (k1 == k2) st.push("YES");
  53.             else st.push("NO");
  54.         }
  55.     }
  56.     while (!st.empty()) {
  57.         cout << st.top() << "\n";
  58.         st.pop();
  59.     }
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement