https://www.acmicpc.net/problem/25489시간 제한메모리 제한4초1536MB문제국렬이는 작년 여름에 사용하다 남은 전구 스트립을 이용해서 자신의 자취방에 있는 N개의 정점으로 이루어진 트리를 장식하려고 한다. 전구는 트리의 각 정점에 하나씩 설치되어 있다. i번째 정점에 붙어있는 전구는 전원을 넣었을 때 p_i의 확률로 켜진다. 그리고 전구에 여유가 넘치는 국렬이는 간선에 추가 전구를 하나씩 달았다. 이 추가 전구들은 연결된 두 정점에 설치된 전구들 중 하나만이 켜졌을 때 불이 켜진다. 추가로 국렬이는 Q번 특정 정점에 설치된 전구를 다른 전구로 바꿀 것이다. 각 시점별로 불이 들어오는 전구 개수의 기댓값을 구하여라. 입력첫 번째 줄에는 정점의 개수 N이 주어진다. (2 ≤ N ..

https://www.acmicpc.net/problem/32251시간 제한메모리 제한2초(추가 시간 없음)1024MB(추가 메모리 없음)문제목이 마른 나무에게 물을 주자! 나무는 N개의 정점과 (N-1)개의 간선으로 이루어져 있으며, 어느 두 정점 간에도 단순 경로가 유일하게 존재하는 그래프를 의미한다. 1번 정점을 나무의 뿌리라고 부르자. 또 i번 정점과 직접 연결되어 있으면서 뿌리와의 단순 경로의 길이가 i번 정점보다 더 큰 정점을 i번 정점의 자식 정점이라고 부르자. 각 정점에는 열매가 하나씩 있다. 열매에 물을 주면 자신의 크기만큼 물을 흡수할 수 있고, 물을 주면 가능한 최대로 흡수한다. 또한 흡수한 물의 양만큼 열매의 크기가 커진다. 자식 정점이 하나 이상 있다면, 열매가 흡수하고 남은 물은..

분리 집합은 두 집합의 관계르 나타내는 것으로 두 집합 A와 B의 교집합이 공집합일 때 A와 B는 분리 집합이라고 한다. 집합의 요소를 놓고 요소들이 포함된 집합이 같은 집합인지 분리 집합인지 확인하고, 두 분리 집합을 하나로 병합하는 알고리즘을 유니온 파인드라고 한다. 1. 분리 집합(Disjoint set) 두 집합 A = {1, 2, 3, 4, 5}와 B = {5, 6, 7, 8, 9}는 '5'를 공통 원소로 갖는다. 이 경우 A, B는 분리 집합이 아니다. 집합 C = {10, 11, 12, 13, 14}가 있을 때, A∪B와 C는 공통 원소가 없는 분리 집합이다. A와 C도 분리 집합이고 B와 C도 분리 집합이다. 여러 정점을 놓고 간선으로 연결한 상태가 주어졌을 때, 정점과 간선을 거쳐 연결된..