Sóc con và bài toán trên cây

Xem PDF

Điểm: 500 Thời gian: 3.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho \(1\) cây gồm \(n\) đỉnh được đánh số từ \(1, 2, \cdots, n\)\(n - 1\) cạnh.

Tại một vị trí \(u\) bất kì thì sóc con có thể nhảy tới \(1\) đỉnh \(v\) sao cho khoảng cách giữa \(u\)\(v\) không quá \(k\).
(Khoảng cách giữa 2 điểm bất kì chính là số cạnh trên đường đi từ đỉnh xuất phát đến đỉnh kết thúc).

Gọi \(f(u, v)\) là số bước tối thiểu để sóc con có thể nhảy từ đỉnh \(u\) đến đỉnh \(v\).
Ví dụ:

  • Với \(k = 2: f(1, 6) = 2, f(2, 5) = 1, f(3, 4) = 1\).

Yêu cầu: Tính tổng các \(f(u, v)\) của mọi cặp đỉnh trên đồ thị với \(u\)\(v\) là 2 cặp đỉnh của đồ thị và \(u \leq v\).

Input

  • Dòng đầu chứa hai số nguyên \(n,k\) - lần lượt là số đỉnh và số \(k\). \((1 \leq n \leq 2 \times 10^5,1 \leq k \leq 500)\)
  • Dòng tiếp theo gồm các số \(p_i: p_1,p_2,p_3,...,p_n\) thể hiện có cạnh nối giữa đỉnh \(i\) và đỉnh \(p_i\).

Nếu \(p_i = 0\) thì đỉnh \(i\) chính là gốc của cây.

Output:

  • Trả về 1 số nguyên dương là kết quả bài toán.

Scoring

  • Subtask \(1\) (\(44,44\%\) số điểm): \((1 \leq n \leq 2 \times 10^3,1 \leq k \leq 500)\)
  • Subtask \(2\) (\(33,33\%\) số điểm): \((1≤n≤2 \times 10^5,1 \leq k \leq 10)\)
  • Subtask \(3\) (\(22,22\%\) số điểm): \((1 \leq n≤2 \times 10^5,1 \leq k \leq 500)\)

Example

Test 1

Input
6 2
4 4 4 0 4 5 
Output
18
Note

Hình vẽ trên ví dụ.
\(f(1, 4) = f(2, 4) = f(3, 4) = f(4, 5) = f(5, 6) = f(1, 2) = f(1, 3) = f(1, 5) = f(2, 3) = f(2, 5) = f(3, 5) = f(4, 6) = 1.\)
\(f(1, 6) = f(2, 6) = f(3, 6) = 2.\)
=> \(12 + 6 = 18.\)


Bình luận


  • -2
    danhtk14    11:03 a.m. 14 Tháng 9, 2021

    f(1, 6) = 3 > k mà?

    đề giải thích lủng củng quá


    • 1
      hvu_1208    8:27 a.m. 17 Tháng 9, 2021

      f(1, 6) = 3 với k = 2 thì f(1, 6) = 2 đúng rồi mà bạn