[백준] 나무 위의 빗물 - 골드5, 트리(Tree)

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

17073번: 나무 위의 빗물

문제이해가 살짝 어려운 문제입니다.

이제 매초마다 모든 정점은 아래의 작업을 순서대로 반복한다.

• 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 동일한 확률로 그 중 하나를 고른다.
• 만약 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아 둔다.

라고 써있어서 처음에 1씩 빼면서 연산하는 줄알았는데

. 더 이상 물이 움직이지 않을 때, i번 정점에 쌓인 물의 양의 기댓값을 Pi라 하자. 

라고 써있어서 나중에 물이 움직이지 않는다는것은 결국 모든 물이 다 내려가야한다는 것을 의미한다고 깨닳았습니다.

 

결국 모든 물은 리프노드로 가게 되어 있으므로 리프 노드의 개수를 구하여 

W / 리프노드의 개수 = 평균값. 이 나옵니다.

 

 

기억해야할점들

첫번째, 루트노드는 제외하고 간선이 1개인 점을 구해야만합니다.

 

코드입니다.

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	static ArrayList<ArrayList<Node>> tree = new ArrayList<ArrayList<Node>>();
	static long[] water;
	static Node root = new Node();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N= sc.nextInt(); int W = sc.nextInt();
		water = new long[N];
		water[1] = W;
		
		for(int i=0;i<=N;i++) {
			tree.add(new ArrayList<Node>());
		}
		
		for(int i=0;i<N-1;i++) {
			int U = sc.nextInt(); int V = sc.nextInt();
			tree.get(U).add(new Node(V));
			tree.get(V).add(new Node(U));
		}
		
		int leafNodeCnt = 0;
		for(int i=2; i<=N; i++) {
			if(tree.get(i).size() == 1) leafNodeCnt+=1;
		}
		System.out.println( (double)W/leafNodeCnt);

	}
	
	

	static class Node{
		int index;
		Node(){
			
		}
		Node(int index){
			this.index = index;
		}
	}
}