CapdoiHH - Cặp đôi hoàn hảo
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: phuleethanh

       Sau khi được NTUcoder tính giúp doanh thu, công ty của Bin ngày càng phát triển nhanh chóng. Số lượng nhân viên lúc này lên đến chục vạn người, phân thành nhiều cấp khác nhau. Công ty của Bin có cơ chế trả lương đặc thù đảm bảo trả đúng theo năng lực. Mỗi người trong công ty được đánh giá bởi một chỉ số năng lực C (0 < C <= số lượng nhân viên) và chỉ số năng lực này cũng được xem là số thứ tự của nhân viên đó trong công ty. Công ty sẽ dựa trên hệ số năng lực này để trả lương cho nhân viên. Ngoài ra công ty còn thường xuyên trả tiền thưởng theo tháng cho nhân viên. Hai nhân viên i và j được gọi là cặp đôi hoàn hảo và sẽ nhận được một khoản tiền thưởng trong tháng đó nếu hai chỉ số năng lực của họ thỏa mãn điều kiện công ty đưa ra:

-  i là cấp trên của j (có thể là cấp trên trực tiếp hoặc cấp trên của cấp trên của j)

-  abs(Ci – Cj) <=k với K là một số do công ty đưa ra.

       Xếp Bin muốn các bạn giúp tính xem trong tháng này thì số lượng cặp đôi hoàn hảo là bao nhiêu để chuẩn bị tiền thưởng.

Input:

  -  Dòng đầu tiên: gồm 2 số nguyên dương N và K là số lượng nhân viên và số K do công ty đưa ra (1 ≤ N, K ≤ 10^5)

  -  n-1 dòng sau: Mỗi dòng là một cặp số nguyên (u,v) tức nhân viên có chỉ số năng lực u là cấp trên trực tiếp của nhân viên có chỉ số năng lực v. (u,v ≤ N)

Ràng buộc:

  - Dữ liệu cho đảm bảo các mối quan hệ tạo thành 1 cây.

Ouput:

  -  Gồm một số nguyên duy nhất là đáp án của bài toán.

Ví dụ

  • input
    5 2
    3 2
    3 1
    1 4
    1 5
    output
    4

Giải thích: có 4 cặp (3,2) (3,1) (3,4) và (3,5)

Back to Top