| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 (추가 시간 없음) | 1024 MB | 135 | 45 | 37 | 31.624% |
종영이는 애완 트리를 키우고 있다. 이 트리는 $N$개의 정점이 있으며 $i$번째 간선은 두 정점 $u_i$와 $v_i$를 잇는다.
요즘 트리에게도 사춘기가 와서, 변덕이 심해 간선들의 길이가 매일 바뀐다. $i$번째 간선의 길이는 $\left[L_i, R_i\right]$ 범위의 자연수의 값들 중 하나를 가질 수 있다.
트리의 변덕에 짜증이 난 종영이는 참을성이 부족해 트리를 팔아버리기로 했다. 트리는 지름이 $S$ 이상 $E$ 이하이면 크기가 적절한 좋은 트리라 생각되어 비싸게 취급된다. 트리의 지름은 트리 상에서 임의의 두 정점 사이의 거리 중 최댓값을 뜻한다.
간선들의 가능한 길이들의 조합은 총 $\prod_{i=1}^{N-1} \left(R_i-L_i+1\right)$가지임을 알 수 있다. 종영이가 트리를 비싸게 팔아치우는 것을 도와주기 위해 가능한 모든 조합에 대해 트리의 지름이 $S$ 이상 $E$ 이하인 경우의 수를 구하여라.
첫 줄에 $N,ドル $S,ドル $E$가 주어진다. (2ドル \leq N \leq 400,ドル 1ドル \leq S \leq E \leq 10^9$)
그 후 $N-1$개의 줄에 걸쳐 트리의 간선들의 정보가 주어진다. 정보는 $u_i,ドル $v_i,ドル $L_i,ドル $R_i$ 순서로 주어진다. (1ドル \leq u_i,ドル $v_i \leq N,ドル 1ドル \leq L_i \leq R_i \leq 400$)
트리의 지름이 $S$ 이상 $E$ 이하인 경우의 수를 10ドル^9+7$로 나눈 나머지를 출력한다.
4 3 14 1 2 1 10 1 3 1 10 1 4 1 10
573
8 17 31 3 4 5 5 1 8 8 8 8 2 8 10 6 7 8 10 6 3 9 10 8 6 7 10 7 5 1 10
159
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2020 F번