VM 10 Bài 05 - Tổng trên cây

Xem dạng PDF
Gửi bài giải
Điểm: 1,19 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
VM10Tác giả: Cosmin Silvestru Negruseri
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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.

Input

  • 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.

Output

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

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.

Sample Input

Copy
5 3
0 1
1 2
2 1
1 -2
4 5

Sample Output

Copy
3

Note

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

Bình luận

Hãy đọc nội quy trước khi bình luận.