[백준 15681] 트리와 쿼리

https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

#include <cstdio>
#include <list>
int N, R, Q;
int query[100000 + 2];
int visited[100000 + 2];

using namespace std;

list<int> Tree[100000 + 2];


void input()
{
	scanf("%d %d %d", &N, &R, &Q);
	for (int i = 0; i < N - 1; i++) {
		int u = 0; int v = 0;
		scanf("%d %d", &u, &v);
		Tree[u].push_back(v);
		Tree[v].push_back(u);
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d", &query[i]);
	}
}


int DFS(int n)
{
	visited[n] = 1;
	for (int nn : Tree[n]) {
		if (visited[nn]) continue;
		visited[n] += DFS(nn);
	}
	return visited[n];	// 리턴하면서 방문배열에 저장된 값 전달		// 리프일 경우 1만 저장
}

void output()
{
	for (int i = 0; i < Q; i++) {
		printf("%d\n", visited[query[i]]);
	}
}

int main()
{
	input();
	DFS(R);	// R은 루트의 번호
	output();
	return 0;
}

 

// DFS( ) 함수

리턴타입을 int로 해준 이유는 노드 n의 방문배열에 저장된 값을 부모 노드로 전달하기 위함이다. 

리프노드는 자연스럽게 방문배열에 들어있는 값이 1이 된다(인접한 노드가 없기 때문에 재귀함수를 콜 할 수 없음). 반면 자식노드를 가진 노드들은 재귀함수를 콜하면서 자식노드들에 저장된 방문배열의 값들을 누적한다. 

 

예제의 입력을 그림으로 그려보면 다음과 같다.