www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 유니온 파인드를 이용해서 문제를 해결했다. 그런데 시간 초과를 해결하기 위해, 쿼리에서 전체 에지(n-1개)를 모두 제거하므로 정점이 모두 분리 되있는 경우부터 거꾸로 생각해 나간다. 즉 거꾸로 가면서 에지를 제거하는 쿼리는 에지를 연결하는 식으로 진행한다 그리고 거꾸로 진행했으므로 결과도 뒤집는다. 코드 #include #include #include #include using name..

www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 전위 순회의 첫 번째가 해당 트리(서브 트리)의 루트 노드라는 것을 구할 수 있고, 구한 루트 노드를 이용해, 중위 순회 결과에서 해당 트리(서브 트리)의 왼쪽 부분의 노드 개수를 구할 수 있다. 이를 통해 해당 트리(서브 트리)를 왼쪽 부분, 오른쪽 부분으로 나눌 수 있다. 코드 #include #include #include using namespace std; int t; int n; vecto..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 부모 노드와 자식 노드의 관계를 나타내는 ischild를 토대로 트리를 만들고, delete_number노드를 지운 뒤, leaf노드의 개수를 구한다. 여기서 주의해야 될 점은 A노드의 자식 노드가 하나인데 그 자식 노드를 지우면 A노드가 leaf노드가 된다는 점이다. 코드 #include #include #include using namespace std; int n; bool ischil..