VM 15 Bài 02 - Cây tiền lương

View as PDF

Submit solution

Points: 0.74 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM15 - Nguyễn Vương Linh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~).

Input

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

Output

  • 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 \leq N \leq 10^{5}~.
  • ~1 \leq C_{i} \leq 10^{9}~.
  • ~20\%~ số test, ~N \leq 100~.
  • ~15\%~ số test, ~N \leq 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 \leq x < N~.
  • ~65\%~ số test, ~N \leq 10^{5}~.

Sample Input

5
3
1 2
1 2
3 2
3 1

Sample Output

6

Note

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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.