34262번 - 트리 위의 표식 서브태스크

문제

정점이 $N$개인 트리가 주어진다. 간선은 $N-1$개이며, $i$번째 간선은 정점 $A_i$와 $B_i$를 길이 $C_i(>0)$인 도로로 연결한다.

트리 위의 지점은 정점뿐만 아니라 간선 위의 임의의 위치까지 포함한다. 트리가 사이클이 없는 구조이므로, 임의의 두 지점 $x, y$ 사이에는 항상 유일한 단순 경로가 존재한다. 두 지점 사이의 거리 $d(x, y)$를 다음과 같이 정의한다.

• $d(x, y)$ = $x$에서 $y$로 가는 단순 경로를 따라 이동할 때 거쳐야 하는 도로의 총 길이
• 특히, $x = y$이면 $d(x, y) = 0$

트리 위에 서로 구분되는 $K$개의 표식이 놓인다. 각 표식은 $N$개의 정점 중 하나를 균등하고 독립적으로 선택하여 위치한다. 즉, 하나의 표식이 임의의 정점 $v$에 있을 확률은 1ドル/N$이다.

트리 위의 표식들이 가깝다는 것은, 모든 표식이 현재 위치에서 최대 $L$만큼 이동해서 트리 위의 어떠한 지점에서 만날 수 있음을 뜻한다. 이 때 지점은 정점 혹은, 간선 위의 어떤 위치일 수 있다.

표식들이 가까울 확률을 구하여라. 확률을 기약분수 $\tfrac{P}{Q}$로 나타냈을 때, 다음 조건을 만족하는 정수 $R$을 출력해야 한다. \[0 \le R < 998244353, \qquad R \cdot Q \equiv P \pmod{998244353}.\] 제한 조건을 만족하는 모든 입력에 대해 $R$이 유일하게 존재함을 보일 수 있다.

입력

첫째 줄에 세 정수 $N,ドル $K,ドル $L$이 공백을 사이에 두고 주어진다.

둘째 줄부터 $N-1$개의 줄에 걸쳐 간선의 정보가 주어진다. 각 줄에는 세 정수 $A_i,ドル $B_i,ドル $C_i$가 주어진다. 이는 $A_i$번 정점과 $B_i$번 정점이 길이 $C_i$​의 간선으로 연결됨을 의미한다.

출력

문제의 조건을 만족하는 정수 \(R\)을 한 줄에 출력한다.

제한

• 1ドル \le N \le 200,000円$
• 1ドル \le K \le 10^{18}$
• 0ドル \le L \le 10^{18}$
• 1ドル \le A_i, B_i \le N$ (1ドル \le i \le N-1$)
• 1ドル \le C_i \le 10^9$ (1ドル \le i \le N-1$)
• 입력으로 주어진 그래프는 트리다.
• 입력으로 주어진 모든 수는 정수다.

서브태스크

힌트