VMSALARY - Cây tiền lương

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

Tại công ty VM15, có N nhân viên được đánh số từ 1. Trong công ty, trừ CEO (nhân viên số 1), nhân viên thứ i luôn có cấp trên trực tiếp là nhân viên thứ j với j < i . Nói cách khác, quan hệ giữa các nhân viên tạo thành một cấu trúc hình cây.

(Cây là đồ thị vô hướng liên thông không có chu trình).

Nếu nhân viên x là cấp trên trực tiếp của nhân viên y và nhân viên y là cấp trên của nhân viên z thì x là cấp trên (nhưng không trực tiếp) của nhân viên z.

Nhân viên thứ i có mức lương là C i . Hãy đếm số bộ ba nhân viên (x, y, z) khác nhau sao cho :

  • Nhân viên thứ x là cấp trên của nhân viên thứ y và thứ z (không cần là cấp trên trực tiếp).
  • Lương của nhân viên thứ x cao hơn lương của nhân viên thứ y và thứ z .
  • Bộ ba (x, y, z) được coi là giống với bộ ba (x, z, y) .

Dữ liệu vào

  • Dòng 1: chứa số nguyên dương N thể hiện số nhân viên.
  • Dòng 2: chứa một số nguyên dương C 1 thể hiện tiền lương của CEO (nhân viên 1).
  • N-1 dòng tiếp theo: dòng thứ i chứa 2 số nguyên dương P i+1 và C i+1 lần lượt thể hiện cấp trên trực tiếp và tiền lương của nhân viên thứ i+1 .

Dữ liệu ra

  • Một số nguyên duy nhất là số lượng bộ ba thỏa mãn.
  • Kết quả có thể vượt quá giới hạn số nguyên 32 bit.

Giới hạn

  • 1 ≤ N ≤ 10 5 .
  • 1 ≤ C i ≤ 10 9 .
  • 20% số test, N ≤ 100.
  • 15% số test, N ≤ 10 5 , nhân viên thứ x là cấp trên của nhân viên thứ x+1 , với 1 ≤ x < N.
  • 65% số test, N ≤ 10 5 .
  • Trong quá trình thi, bài của bạn sẽ chỉ được chấm với test ví dụ.

Ví dụ

Input

5
3
1 2
1 2
3 2
3 1

Output

6

Giải thích

Sơ đồ biểu diễn cấp bậc của các nhân viên sẽ như sau:

  1
 /  \
2    3
     /  \
   4    5

Ta có 6 bộ ba như sau:

  1. (1, 2, 3) - Nhân viên thứ nhất có lương bằng 3 lớn hơn nhân viên thứ 2 và thứ 3 với tiền lương của mỗi người là 2. Nhân viên 1 đều là cấp trên của nhân viên 2 và 3.
  2. (1, 2, 4) - Tiền lương của nhân viên thứ 2 và thứ 4 đều là 2 và nhỏ hơn tiền lương của CEO và cả 2 đều là cấp dưới.
  3. (1, 2, 5)
  4. (1, 3, 4)
  5. (1, 3, 5)
  6. (1, 4, 5)

Bộ (3, 4, 5) không được tính vì lương của nhân viên thứ 3 chỉ bằng chứ không cao hơn tiền lương của nhân viên thứ 4.

  • Người up: voj
  • Nguồn bài: VM15 - Nguyễn Vương Linh