{"code":"sctree","name":"Cây cùng màu","description":"[user:ami] có một đồ thị dạng cây gồm $n$ nút, mỗi nút được đánh số từ 1. Nút $i$ được tô màu $a_i$.\r\n\r\n[user:ami] cần các bạn tính tổng tất cả đường đi ngắn nhất giữa hai nút u và v được tô cùng một chung màu. Tổng có thể được biểu diễn như sau:\r\n\r\n$\\sum dist(u , v)$  $\\forall$ $u \\leq v$ và $a_u = a_v$.\r\n\r\nTrong đó, $dist(u , v)$ là độ dài đường đi ngắn nhất giữa hay nút $u$ và $v$. Độ dài một đường đi từ u đến v được tính bằng tổng số cạnh nằm trên đường đi đó.\r\n\r\n<h4>Input</h4>\r\n\r\n- Dòng đầu tiên chứa số nguyên dương $n$ là số đỉnh của cây.\r\n\r\n- Dòng tiếp theo chứa $n$ số nguyên dương $a_i$ biểu thị một màu của đỉnh $i$.\r\n\r\n- $n$ dòng tiếp theo, môi dòng chứa $2$ số nguyên dương $u$ và $v$ biểu thị một cạnh nối giữa hai đỉnh $u$ và $v$.\r\n\r\n<h4>Output</h4>\r\n\r\n- Hãy in ra tổng cần tìm\r\n\r\n<h4>Scoring</h4>\r\n\r\n- Subtask $1$ ($18\\%$ số điểm): $1 \\leq n \\leq 10$ và $1 \\leq a_i \\leq 3*10^5$.\r\n\r\n- Subtask $2$ ($18\\%$ số điểm): $1 \\leq n \\leq 1000$ và $1 \\leq a_i \\leq 3*10^5$.\r\n\r\n- Subtask $3$ ($18\\%$ số điểm): $1 \\leq n \\leq 3*10^5$ và $1 \\leq a_i \\leq 10$.  \r\n\r\n- Subtask $4$ ($46\\%$ số điểm): $1 \\leq n \\leq 3*10^5$ và $1 \\leq a_i \\leq 3*10^5$.  \r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4\r\n        1 3 1 3\r\n        1 2\r\n        2 3\r\n        2 4\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```\r\n    \r\n    ??? warning \"Note\"\r\n\r\n        Ở ví dụ 1, đồ thị cây có dạng như sau:\r\n\r\n        ![tree][1]\r\n\r\n        Các đỉnh cùng màu là (1 , 3) và (2 , 4). Do đó, $dist(1 , 3)$ + $dist(2 , 4)$ = 2 + 1 = 3\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        9\r\n        1 1 1 2 3 2 2 1 1 \r\n        1 2\r\n        2 3\r\n        3 4\r\n        3 5\r\n        4 6\r\n        3 7\r\n        7 8\r\n        7 9\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        30\r\n        ```\r\n    \r\n    ??? warning \"Note\"\r\n\r\n        Ở ví dụ 2, đồ thị cây có dạng như sau:\r\n\r\n        ![tree2][2]\r\n\r\n[1]: https://i.imgur.com/PyTROkR.png\r\n\r\n[2]: https://i.imgur.com/MM8cu8r.png","points":500.0,"partial":false,"time_limit":1.0,"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}}