32117번 - $\prod_{i=1}^N(R_i-L_i+1)$개의 트리

문제

1ドル$번 정점을 루트로 하는 정점 $N$개의 트리가 주어진다. 우리는 각 정점에 쓰일 음이 아닌 정수 $a_i$를 정할 것이다.

이때 $a_i$들은 다음 조건을 만족해야 한다. 모든 1ドル\leq i\leq N$에 대해서,

• $a_i\leq p_i$
• $i$번 서브트리 내부의 정점 $j$에 대해서 $a_j$를 모두 더한 값을 $S_i$라고 했을 때, $S_i\geq q_i$

위의 조건을 만족하는 $(a_1,a_2,\ldots ,a_N)$에 대해 $\sum_{i=1}^Nc_{i}a_{i}$의 최솟값을 $f(c_1,c_2,\ldots ,c_N)$으로 정의하자.

다음 값을 998ドル,円 244,円 353$으로 나눈 나머지를 구하여라.

\[\sum_{c_1=L_1}^{R_1}\sum_{c_2=L_2}^{R_2}\cdots\sum_{c_N=L_N}^{R_N}f(c_1,c_2,\cdots ,c_N)\]

입력

첫 줄에 정점의 개수 $N$이 주어진다. (1ドル\leq N\leq 250$)

둘째 줄부터 $(N-1)$개의 줄에 걸쳐 트리 간선에 대한 정보가 주어진다. 이중 $i$번째 줄에는 두 개의 정수 $s_i,ドル $e_i$가 공백으로 구분되어 주어진다. (1ドル\leq s_i,e_i\leq N$) 이는 $s_i$와 $e_i$를 잇는 간선이 존재한다는 것이다.

1ドル\leq i\leq N$에 대해, $(N+i)$번째 줄에는 $p_i,ドル $q_i,ドル $L_i,ドル $R_i$가 공백을 사이에 두고 주어진다. (1ドル\leq L_i\leq R_i\leq 250$; 0ドル\leq p_i,q_i\leq 250$; $\sum_{i=1}^Np_i\leq 250$)

주어진 그래프는 트리를 이루며, 주어진 조건을 만족하는 $(a_1,a_2,\ldots ,a_N)$이 존재하는 입력만이 주어진다.

출력

문제에 주어진 값을 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다. 998ドル,円 244,円 353=119\times 2^{23}+1$은 소수이다.

제한

노트

$j$번 정점이 $i$번 서브트리 내부에 포함된다는 것은 $j=i$이거나 $i$번 정점이 $j$번 정점의 조상이라는 것이다.