Submission #544688

#TimeUsernameProblemLanguageResultExecution timeMemory
544688pokmui9909트리 (KOI16_treeM)C++17
100 / 100
135 ms21920 KiB
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll n, Q;
ll p[200005];
vector<ll> ans;
 
struct st
{
	ll t, x, y;
}qry[400005];
 
ll uf[200005];
 
ll Find(ll n)
{
	if (uf[n] == -1) return n;
	return uf[n] = Find(uf[n]);
}
 
void Union(ll x, ll y)
{
	x = Find(x), y = Find(y);
	uf[y] = x;
}
 
int main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
 
	cin >> n >> Q;
	fill(uf, uf + 200005, -1);
	for (ll i = 2; i <= n; i++) cin >> p[i];
	for (ll i = 1; i < n + Q; i++)
	{
		ll op; cin >> op;
		if (op == 0)
		{
			ll x; cin >> x;
			qry[i] = { 0, x, 0 };
		}
		else
		{
			ll x, y; cin >> x >> y;
			qry[i] = { 1, x, y };
		}
	}
	for (ll i = n + Q - 1; i >= 1; i--)
	{
		if (qry[i].t == 0) Union(qry[i].x, p[qry[i].x]);
		else ans.push_back(Find(qry[i].x) == Find(qry[i].y));
	}
	reverse(ans.begin(), ans.end());
	for (auto i : ans) cout << (i ? "YES\n" : "NO\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...