27383번 - 알록달록 트리

문제

작년 크리스마스에 예쁜 크리스마스 트리를 보고 감명받은 윤헌이는 우정정보관 앞에 $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円$로 나눈 나머지를 출력한다.

제한

• 1ドル \le n \le 10^5$
• 1ドル \le k \le 10^5$
• 0ドル \le l_i \le r_i \le \min(k, d_i)$ (단, $d_i$는 $i$번 정점의 자식의 수)

힌트