Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
- #define a first
- #define b second
- using namespace std;
- const int MAXN = 2 * 1e6 + 1;
- typedef pair<pair<int, int>, pair<int, int>> pai;
- int n, q, parent[MAXN], fparent[MAXN], lvl[MAXN];
- vector<pai> v;
- stack<string> st;
- int find(int u) {
- if (u == parent[u]) return u;
- return parent[u] = find(parent[u]);
- }
- void merge(int u, int v) {
- u = find(u);
- v = find(v);
- if (u == v) return;
- if (lvl[u] > lvl[v]) swap(u, v);
- parent[u] = v;
- lvl[v] += lvl[u];
- }
- int main() {
- fastio;
- cin >> n >> q;
- for (int i = 1; i <= n; i++) {
- parent[i] = i;
- lvl[i] = 1;
- }
- for (int i = 2; i <= n; i++) cin >> fparent[i];
- fparent[1] = 1;
- for (int x, a, b, i = 0; i < n - 1 + q; i++) {
- cin >> x;
- if (!x) {
- cin >> a;
- v.push_back({ {x,a},{0,0} });
- }
- else {
- cin >> a >> b;
- v.push_back({ {x,0},{a,b} });
- }
- }
- std::reverse(v.begin(), v.end());
- for (int i = 0; i < v.size(); i++) {
- int x = v[i].a.a;
- if (x == 0) {
- int k = v[i].a.b;
- merge(k, fparent[k]);
- }
- else {
- int k1 = find(v[i].b.a), k2 = find(v[i].b.b);
- if (k1 == k2) st.push("YES");
- else st.push("NO");
- }
- }
- while (!st.empty()) {
- cout << st.top() << "\n";
- st.pop();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement