[13306] 트리

https://www.acmicpc.net/problem/13306

13306번: 트리

---

#include <bits/stdc++.h>

using namespace std;

class UF {

   public:

    vector<int> p;

    UF(int n) { p = vector<int>(n + 1, -1); }

    int find(int cur) {

        if (p[cur] < 0) return cur;

        return p[cur] = find(p[cur]);

    }

#define union _union

    void union(int A, int B) {

        A = find(A), B = find(B);

        if (A == B) return;

        if (p[A] < p[B])

            p[A] += p[B], p[B] = A;

        else

            p[B] += p[A], p[A] = B;

    }

};

int n, Q;

vector<int> v;

typedef struct {

    int op, a, b;

} qry;

vector<qry> q;

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> Q;

    v.resize(n + 1);

    auto uf = UF(n);

    int i;

    v[1] = 1;  // root

    for (i = 2; i <= n; i++) cin >> v[i];

    int S = n - 1 + Q;

    q.resize(S);

    for (i = 0; i < S; i++) {

        qry cur = {-1, -1, -1};

        cin >> cur.op;

        if (cur.op == 1)

            cin >> cur.a >> cur.b;

        else if (cur.op == 0)

            cin >> cur.a;

        q[i] = cur;

    }

    stack<bool> ans;

    for (i = S - 1; i >= 0; i--) {

        qry cur = q[i];

        if (cur.op == 0)

            uf.union(cur.a, v[cur.a]);

        else if (cur.op == 1)

            ans.push((uf.find(cur.a) == uf.find(cur.b)));

    }

    while (!ans.empty()) {

        cout << (ans.top() ? "YES" : "NO") << '\n';

        ans.pop();

    }

    return 0;

}

---