[C++]백준 15681번 : 트리와 쿼리

문제 출처

풀이

DFS로 풀면 쉽게 풀리는 문제이다. root부터 시작해서 leaf까지 DFS를 한다. leaf의 서브트리에 속한 정점의 수는 1이므로 이것들을 다 더해서 root까지 보내주면 완성이다. 사실 이 문제 밑에 있는 내용이 꽤 유익해서 한번쯤 읽어보는 것을 추천한다. 다음은 전체 코드이다

#include<iostream>
#include<vector>

using namespace std;

void MakeTreeSize(vector<vector<int>> &adj, vector<int> &totalsize,int now , int parent) {
	int size = 1;
	for ( int child : adj[now] ) {
		if ( child == parent )continue;
		MakeTreeSize(adj, totalsize,child, now);
		size += totalsize[child];
	}
	totalsize[now] = size;
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N, R, Q;
	cin >> N >> R >> Q;
	vector<vector<int>> adj(N + 1, vector<int>());
	vector<int> size(N + 1, 0);
	for ( int i = 0; i < N - 1; i++ ) {
		int U, V;
		cin >> U >> V;
		adj[U].emplace_back(V);
		adj[V].emplace_back(U);
	}
	
	MakeTreeSize(adj, size, R, -1);
	
	for ( int i = 0; i < Q; i++ ) {
		int t;
		cin >> t;
		cout << size[t] << '\n';
	}
	return 0;
}

정말 단순하게 DFS로 하니 쉽게 풀렸다. 단지

cout << size[t]<< endl;

로 처음에 작성하니까 시간초과가 나왔다.
따라서

cout << size[t]<< '\n';

으로 바꿨다. 출력이 많으니 이 부분을 최적화하는 것이 중요했다.