Giải bài trực tuyến

Cho một cây N đỉnh, trong đó đỉnh i có giá trị là Vi. Cho một số nguyên S. Gốc của cây là đỉnh 1. Đếm số đường đi từ một đỉnh u đến một đỉnh v nào đó, với điều kiện u phải nằm trên đường đi từ v đến gốc, sao cho tổng giá trị của các nút trên đường đi bằng S.

Dữ liệu

• Dòng đầu tiên chứa hai số N và S
• Dòng thứ i trong số N dòng tiếp theo chứa hai số Pi, Vi là đỉnh cha của đỉnh i và giá trị của đỉnh i. Ta quy ước P1 = 0.

Giới hạn

• 1 <= N <= 1000000
• Mọi tổng giá trị của các nút trên đường đi từ u đến v, trong đó u nằm trên đường đi từ v đến gốc, luôn nằm trong phạm vi số nguyên 32 bit có dấu.

Kết quả

In ra một số duy nhất là số đường đi tìm được.

Ví dụ

Dữ liệu
5 3
0 1
1 2
2 1
1 -2
4 5

Kết quả
3

Giải thích

Có 3 đường đi là 1-2, 2-3, 4-5