시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 16 | 7 | 5 | 38.462% |
작년 크리스마스에 예쁜 크리스마스 트리를 보고 감명받은 윤헌이는 우정정보관 앞에 $n$개의 예쁜 구슬들이 장식된 "알록달록 트리"를 세우기로 결심했다!
윤헌이는 $n$개의 구슬마다 번호를 붙여 트리 그래프의 정점으로 간주하고, 각 정점에 $k$개의 색 중 하나를 칠하려고 한다. 이때 루트는 $1$번 정점으로 간주한다. 그러나 아무렇게나 정점들을 색칠한 트리는 윤헌이의 마음에 들지 않는다. 윤헌이의 마음에 드는 "알록달록 트리"를 만들기 위해서는, 임의의 정점은 그 정점의 자식들의 색 중에서 하나를 골라 칠해야만 한다. 이때 해당 정점이 리프인 경우 $k$개의 색 중 어떤 색이든 칠할 수 있다.
$i$번 정점의 자식에 칠할 수 있는 색의 가짓수가 $l_i$ 이상 $r_i$ 이하의 범위로 주어질 때, 윤헌이가 세울 수 있는 알록달록 트리의 가짓수를 $998\,244\,353$로 나눈 나머지를 구하시오.
첫 줄에 $n, k$가 공백으로 구분되어 주어진다.
다음 $n-1$개의 줄에 걸쳐 트리의 간선의 양 끝점에 해당하는 정점 번호 $u, v$가 공백으로 구분되어 주어진다.
그다음 $i$번째 줄에는 $i$번 정점의 자식에 칠할 수 있는 색의 가짓수 범위를 나타내는 두 정수 $l_i, r_i$이 공백을 두고 주어진다. 이는 $l_i$ 이상 $r_i$개 이하의 가짓수로 $i$번째 정점의 자식들을 칠해야 함을 의미한다.
트리를 색칠하는 경우의 수를 $998\,244\,353$로 나눈 나머지를 출력한다.
3 3 1 2 1 3 1 2 0 0 0 0
15
$2$번, $3$번 정점은 리프 정점이므로 $3$개의 색 중 아무거나 칠할 수 있다. $1$번 정점은 두 개의 자식을 가지고, 그 자식들은 $1$개 이상 $2$개 이하의 색의 가짓수를 가질 수 있으므로 어떤 색이든 칠할 수 있다.
$2$번, $3$번 정점이 같은 색인 경우 $3$가지, $2$번, $3$번 정점이 다른 색인 경우 $12$가지이므로 전체 가짓수는 $15$가지이다.
5 4 1 2 1 3 2 4 2 5 1 2 1 2 0 0 0 0 0 0
196
University > 고려대학교 > 2022 고려대학교 프로그래밍 경시대회 (KCPC mini) > Div. 1 C번
University > 고려대학교 > 2022 고려대학교 프로그래밍 경시대회 (KCPC mini) > Open Contest I번