[C++] 백준 17073 - 나무 위의 빗물

문제

 

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

---

풀이

 

단순히 (W / leaf의 개수)의 값만 구하면 돼서 트리를 구현할 필요 없이 연결된 간선의 개수가 1인 노드의 개수를 구하면 되는 문제. 문제에서 N의 범위가 2 이상이라 하였으므로 노드가 한 개일때의 예외 케이스는 관리하지 않아도 됨.

 

#include <cstdio>
using namespace std;

int N, U, V; 
double W, leafCnt = 0;
int edgeCnt[500001] = { 0 };

int main() {
	scanf("%d %lf", &N, &W);

	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d", &U, &V);
		edgeCnt[U]++;
		edgeCnt[V]++;
	}

	for (int i = 2; i <= N; i++) {
		if (edgeCnt[i] == 1) {
			leafCnt++;
		}
	}

	printf("%lf", W / leafCnt);
	return 0;
}