[Medium] KingdomXCitiesandVillages

expectation 의 선형성을 이용해 문제를 단순화시킬 수 있다 E( sum( 마을 i를 골랐을 때 선택된 도로의 길이 ), for all i ) = sum( E( 마을 i를 골랐을 때 선택된 도로의 길이 ) ), for all i 결국 각 마을 i에 대해 선택된 도로의 길이의 기대값을 구해서 다 더해주는 문제로 바뀌게 된다. 마을 i를 제외한 나머지 마을, 그리고 모든 city에 대해 거리를 구한 다음 오름차순으로 정렬해놓은 배열 s[] 를 만들자. s[] 의 앞에서부터 city가 처음 등장하기 전 까지의 모든 village와 처음 등장한 city가 답을 구할 때 고려된다. 나머지는 버린다. j번째에 위치한 village와 도로를 연결할 확률은 어떻게 될까? 이렇게 되려면 0~j-1번째 village는 마을 i가 선택된 이후에 선택되어야 하고, j번째 village는 마을 i가 선택되기 전에 선택되어야 한다. 이걸 일렬로 늘어놓고 이렇게 될 확률을 구해보면 j! / (j+2)! = 1 / (j+1)(j+2) 이다. j번째에 위치한 city와 도로를 연결할 확률은 어떻게 될까? 이렇게 되려면 0~j-1번째 village는 마을 i가 선택된 이후에 선택되어야 한다. 마찬가지로 생각해보면 확률은 j! / (j+1)! = 1 / (j+1) 이다.