https://www.acmicpc.net/problem/32251
| 시간 제한 | 메모리 제한 |
| 2초(추가 시간 없음) | 1024MB(추가 메모리 없음) |
문제
목이 마른 나무에게 물을 주자!
나무는 N개의 정점과 (N-1)개의 간선으로 이루어져 있으며, 어느 두 정점 간에도 단순 경로가 유일하게 존재하는 그래프를 의미한다. 1번 정점을 나무의 뿌리라고 부르자. 또 i번 정점과 직접 연결되어 있으면서 뿌리와의 단순 경로의 길이가 i번 정점보다 더 큰 정점을 i번 정점의 자식 정점이라고 부르자.
각 정점에는 열매가 하나씩 있다. 열매에 물을 주면 자신의 크기만큼 물을 흡수할 수 있고, 물을 주면 가능한 최대로 흡수한다. 또한 흡수한 물의 양만큼 열매의 크기가 커진다.
자식 정점이 하나 이상 있다면, 열매가 흡수하고 남은 물은 간선으로 이어진 자식 정점으로 나눠서 흘러간다.
이때 각 자식 정점에게 흘러가는 물의 양은 (남은물의양 // 자식정점의수)이다.
나무에게 물을 주기 위해 Q개의 쿼리를 수행하라.
- 1 u x: 정점 u에 x만큼의 물을 준다. (1 ≤ u ≤ N; 1 ≤ x ≤ 109)
- 2 u: 정점 u의 열매의 크기를 출력한다. (1 ≤ u ≤ N)
입력
첫째 줄에 정점의 개수 N과 쿼리의 개수 Q가 공백을 사이에 두고 주어진다. (1 ≤ N ≤ 100,000; 1 ≤ Q ≤ 100,000)
둘째 줄부터 (N-1)개의 줄에 걸쳐 간선을 이루는 두 정점 u와 v가 공백을 사이에 두고 주어진다. (1 ≤ u,v ≤ N; u ≠ v)
(N+1)째 줄에는 각 정점의 열매의 크기를 의미하는 N개의 양의 정수 x1, x2, …, xN이 공백을 사이에 두고 주어진다. (1 ≤ xi ≤ 109)
(N+2)째 줄부터 Q개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 1 u x 또는 2 u이다. (1 ≤ u ≤ N; 1 ≤ x ≤ 109)
모든 입력은 정수이고, 2번 쿼리는 한 번 이상 주어진다.
출력
주어진 2번 쿼리마다, 해당 쿼리의 정답을 한 줄에 하나씩 출력한다.
풀이
그냥 있는 그대로 구현하면 끝인 문제입니다.
먼저 트리의 모든 정점에서 자식 노드의 정보를 확인하기 위해 1을 루트로 하여 완전탐색 합니다. 이후 입력되는 쿼리에 따라 열매의 크기를 바꾸고, 남은 물을 자식노드의 수로 나누어 물의 양이 0보다 크다면 자식노드에 물을 주는 작업을 반복합니다.
정답 코드
import sys
from collections import deque
input = sys.stdin.readline
def solution():
n, q = map(int, input().split())
link = [[] for _ in range(n + 1)]
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
link[u].append(v)
link[v].append(u)
check = [0] * (n + 1)
check[1] = 1
bfs = deque([1])
while bfs:
now = bfs.popleft()
for next in link[now]:
if check[next]: continue
tree[now].append(next)
check[next] = 1
bfs.append(next)
fruit = [0] + list(map(int, input().split()))
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
water = deque([(query[1], query[2])])
while water:
u, x = water.popleft()
k = min(fruit[u], x)
fruit[u] += k
x -= k
if len(tree[u]):
x //= len(tree[u])
if x:
for next in tree[u]:
water.append((next, x))
else:
print(fruit[query[1]])
solution()