BOJ 13306 - 트리

그냥 문제가 너무 길다. 

 

문제를 요약하자면 모든 정점들이 어느 한 정점으로 연결되어 있는 트리가 있고 두가지 쿼리가 주어진다.

1. 두 정점의 간선을 끊는다

2. 선택한 정점과 연결된 정점들의 개수를 센다.

 

일반적인 방법으로는 문제를 해결하기에는 어려워보인다.

1번 쿼리는 n-1개 들어오기 때문에 최종 상태에서는 모든 정점들이 서로 연결되어 있지 않음을 알 수 있다.

그러면 여기서 쿼리를 거꾸로 수행해보고 싶은 생각이 들 수 있다.

간선을 끊는 쿼리를 구현하는 것은 어려우므로 쿼리를 거꾸로 실행하게 되면 간선을 추가하는 쿼리로 바뀌게 된다!

여기서 바로 유니온 파인드를 사용할 수 있다.

1번 쿼리가 들어오면 두 정점을 유니온 하고 2번 쿼리가 들어오면 연결된 정점들의 개수를 세어주기만 하면 된다.

정점들의 개수는 루트 노드가 되는 정점에 정보를 저장한다. 

 

오프라인 쿼리를 구성하는 방법을 연습하기 좋은 문제였다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <ext/rope>
#include <cassert>
#include <x86intrin.h>
using namespace std;
using namespace __gnu_cxx;

// utils
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define repair(x) x.erase(unique(all(x)),x.end())
typedef long long ll; //long long. or use int64_t
typedef long double ld; //long double
const int iinf = 1e9; //integer maximum
const long long linf = 1e18; //long long maximum
const int mod = 1e9 + 7; //prime number

// gcd, lcm, egcd funcs
template<class T>T gcd(T x, T y){if (!y)return x;return gcd(y,x%y);}
template<class T>T lcm(T x, T y){return (x*y)/gcd(x,y);}
template<class T>tuple<T,T,T> egcd(T a, T b){
	if(b==0)return {a,1,0};
	auto[g,x,y]=egcd(b,a%b);
	return {g,y,x-(a/b)*y};
}
// builtin funcs
template<class T>T bitcnt(T x){return __builtin_popcount(x);}
template<class T>T bitpar(T x){return __builtin_parity(x);}
template<class T>T bitclz(T x){return __builtin_clz(x);}
template<class T>T bitctz(T x){return __builtin_ctz(x);}
// debuging funcs
#define deb(x) cout<<#x<<": "<<(x)<<endl
//////////////////////////////////////////
struct ds{
	vector<int>par;
	int n;
	ds(int N){
		n=N;
		par.resize(n);
		iota(all(par),0);
	}
	int find(int x){
		if(x==par[x])return x;
		return par[x]=find(par[x]);
	}
	void uni(int x, int y){
		x=find(x);y=find(y);
		par[x]=y;
	}
};
int main(){
	fastio;
	int n,q;
	cin>>n>>q;
	vector<int>arr(n+1);
	for(int i=2; i<=n; i++)cin>>arr[i];
	ds dst(n+1);
	q+=n-1;
	vector<tuple<int,int,int>>query;
	int a,b,c=-1;
	while(q--){
		cin>>a;
		if(a==0)cin>>b;
		else cin>>b>>c;
		query.push_back({a,b,c});
		c=-1;
	}
	reverse(all(query));
	vector<string>ans;
	for(auto[a,b,c]:query){
		if(a==0)dst.uni(b,arr[b]);
		else{
			if(dst.find(b)==dst.find(c))ans.push_back("YES");
			else ans.push_back("NO");
		}
	}
	reverse(all(ans));
	for(auto&v:ans)cout<<v<<endl;
	return 0;
}