Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmsalary


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ứ  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à Ci. 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 C1 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 Pi+1 và Ci+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

  • ≤ N ≤ 105.
  • 1 ≤ Ci ≤ 109.
  • 20% số test, N ≤ 100.
  • 15% số test, N ≤ 105, 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 ≤ 105.
  • 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.


Được gửi lên bởi:VOJ Team
Ngày:2015-07-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VM15 - Nguyễn Vương Linh

hide comments
2021-08-08 10:49:07
.
2019-09-14 05:32:16
Find-Union =))
2017-10-26 14:32:20
kham khảo lời giải ở:
https://vietcodes.github.io/code/95/
2017-10-18 08:44:39 minhsn
ko trau dc :((
2016-08-10 16:40:50 nguyenngocanh
BIT + DFS ._.

Last edit: 2016-08-11 06:14:57
2016-07-27 14:08:11
hld
2016-06-08 11:00:48
PLACE + YPKTH :v
2015-11-24 08:23:21 TyT
Place + Kquery :3
2015-08-08 16:45:56 *
lừa tinh ! số nguyên 32bit :v
2015-08-03 09:30:58 vo quoc thang
Cây BIT 100d ^.^
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.