{"code":"jumping","name":"Sóc con và bài toán trên cây","description":"Cho $1$ cây gồm $n$ đỉnh được đánh số từ $1, 2, \\cdots, n$ và $n - 1$ cạnh.\r\n\r\nTạ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à $v$ không quá $k$.\r\n(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).\r\n\r\nGọ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$.\r\n**Ví dụ:**\r\n![](https://i.imgur.com/QqbLMuj.png)\r\n\r\n- Với $k = 2: f(1, 6) = 2, f(2, 5) = 1, f(3, 4) = 1$.\r\n\r\n**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à $v$ là 2 cặp đỉnh của đồ thị và $u \\leq v$.\r\n\r\n#### Input\r\n- 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)$\r\n- 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$.\r\n\r\nNếu $p_i = 0$ thì đỉnh $i$ chính là gốc của cây.\r\n\r\n#### Output:\r\n- Trả về 1 số nguyên dương là kết quả bài toán.\r\n#### Scoring\r\n- Subtask $1$ ($44,44\\%$ số điểm): $(1 \\leq n \\leq 2 \\times 10^3,1 \\leq k \\leq 500)$\r\n- Subtask $2$ ($33,33\\%$ số điểm): $(1≤n≤2 \\times 10^5,1 \\leq k \\leq 10)$\r\n- Subtask $3$ ($22,22\\%$ số điểm): $(1 \\leq n≤2 \\times 10^5,1 \\leq k \\leq 500)$\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6 2\r\n        4 4 4 0 4 5 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        18\r\n        ```\r\n    ??? warning \"Note\"\r\n\r\n        Hình vẽ trên ví dụ.\r\n        $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.$\r\n        $f(1, 6) = f(2, 6) = f(3, 6) = 2.$\r\n        => $12 + 6 = 18.$","points":500.0,"partial":false,"time_limit":3.5,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}