Nguồn: (Dựa trên bài PLANTING trên http://cope-edu.com/).
Rating : 2600.

**Đề Bài**:
Cubill là một học sinh chăm ngoan và được bố cho đi du học ở thành phố Hnincab tại miền đông nước Anh. Do chưa quen với việc sống ở một nơi xa lạ như thế, hơn nữa cậu cũng không quen với giờ học tại đây nên cậu xin bố cậu cho cậu được phép chuyến trường. Sau một hồi suy nghĩ bố cậu không thấy trường nào đủ tốt để yên tâm cho cậu theo học nên bố cậu quyết định tự xây cho cậu một ngôi trường rồi mua một căn nhà gần trường để cậu có thể đi học đúng giờ.

Thành phố Hnincab nơi mà bố con Cubill sinh sống bao gồm $n$ khu vực nhỏ độc lập. Có tất cả $n-1$ con đường hai chiều để đi lại giữa những khu vực này, tất nhiên từ một khu vực bất kì có thể đến được bất cứ khu vực nào khác trong thành phố. Con đường thứ $i$ nối giữa khu vực $u_i$ và $v_i$, cần $t_i$ phút để đi qua con đường này. Thời gian để đi từ khu vực $x$ đến khu vực $y$ sẽ là $d$ phút, với $d$ là tổng các $t_i$ trên các con đường từ $x$ đến $y$.

Cubill để tránh việc đi muộn như ở trường cũ cậu quyết tâm sẽ dậy sớm trước $h$ giờ $p$ phút trước giờ vào học để kịp đi. Việc chọn xây trường và mua nhà ở khu vực nào thực sự làm bố cậu rất mệt mỏi nên Cubill nhờ bạn đếm giúp bố cậu xem có bao nhiêu cách chọn hai khu vực khác nhau để xây trường và mua nhà để cậu vẫn đến đúng giờ học.

Note: Chọn xây trường ở khu vực $x$ và mua nhà của khu vực $y$ là khác với cách chọn
xây trường ở khu vực $y$ và mua nhà của khu vực $x$.
**Input**:
* Dòng đầu chứa ba số nguyên dương $n$, $h$, $p$ ($1\le n \le 10^5$, $1\le h \le 16666666$, $1\le p \le 59$)
* $n-1$ dòng tiếp theo mỗi dòng chứa ba số nguyên $u_i$, $v_i$, $t_i$ ($1\le u_i, v_i \le n$, $1\le t_i \le 10^9$) mô tả một đường đi.

**Output**:

* Một số nguyên dương duy nhất là số cách chọn hai khu vực để xây trường và mua nhà.

**Scoring:**

| Subtask | Điểm | Giới Hạn |
| -------- | -------- | -------- |
| 1 | 30 | $n \le 10^3$ |
| 1 | 30 | $h \le 1666$ |
| 2 | 40 | Không có ràng buộc gì thêm |

**Lời Giải:**
Subtask 1:
Ta thực hiện DFS từ mọi điểm coi điểm đó là khu vực để xây trường rồi đếm xem có bao nhiêu khu vực có thể mua nhà mà Cubill không đi học muộn.(Dĩ nhiên ta sẽ xét thời gian dậy sớm của Cubill trên phút là $h*60+p$).
Đpt: ($n^2$)
**Lưu ý**: Đối Với subtask 2, 3 các bạn cần phải biết Centroid Decomposition để có thể hiểu được. Nếu các bạn chưa học các bạn có thể lên vnoj wiki để đọc.
Subtask 2:
Do $h \le 1666$ nên $h*60+p \le 10^5+19$, gọi $f=h*60+p$.
Giả sử $c$ là centroid của cây mà ta đang xét, ta sẽ thực hiện DFS 2 lần, một để cập nhật những đường mới mà ta vừa xét , lần DFS còn lại ta sẽ tính những đường đi thỏa mãn. Giả sử thời gian đi từ $c$ đến khu vực mà ta đang xét là $v$ như vậy ta còn f-v phút cho Cubill đi học nên ta sẽ tính số lượng đường đi từ tập những đường đi từ $c$ mà ta đã đi qua mà thời gian đi qua đường đi đó bé hơn $f-v$. Để tiện cho việc cập nhật và tính số đường đi bé hơn $f-v$ ta có thể sử dụng những ctđl về cây.
Subtask 3:
Do $h \le 16666666$ nên $h*60+p \le 10^9+19$, ta làm y như subtask 2 nhưng ở đây $f$ khá lớn nên ta phải sử dụng Trie hoặc Dynamic segment tree.

Đpt ($n.log n. logf$).

**Code:** https://ideone.com/BBpsJY