{"code":"diffgraph","name":"Bài tập Wu Zi Mu","description":"Một ngày, giáo sư Wu Zi Mu đã ra một bài tập mang tính \"giải trí\" cho các học sinh lớp $1$ như sau:\r\n\r\n\"Cho $N$ cái thùng chứa đựng đồ chơi, thùng thứ $i$ chỉ chứa loại đồ chơi mang số $C_i$, và có $N-1$ con đường để di chuyển trực tiếp hai thùng đồ chơi. Đảm bảo rằng tồn tại đường đi duy nhất giữa hai thùng đồ chơi bất kỳ.\r\n\r\nTa định nghĩa $D(u, v)$ là số loại đồ chơi khác nhau trên đường đi giữa hai thùng đồ chơi $u$ và $v$. Với mỗi thùng đồ chơi $u$, giáo sư muốn tính toán $Sum(u) = \\sum\\limits_{v=1}^N D(u, v)$.\r\n\r\nYêu cầu của các học sinh là xác định tất cả các $Sum(u)$, với $1 \\leq u \\leq N$.\"\r\n\r\nHọc sinh rất là bối rối với bài tập này, không biết làm như thế nào cả. Các bạn giúp các học sinh thực hiện bài tập \"giải trí\" trên.\r\n\r\n#### Input\r\n- Gồm $N + 1$ dòng:\r\n+ Dòng thứ nhất gồm số nguyên dương $N$ là số thùng đồ chơi.\r\n+ Dòng thứ hai chứa $N$ số nguyên dương $C_1, C_2, C_3, ..., C_N$, với $C_i$ là loại đồ chơi ở thùng thứ $i$.\r\n+ $N - 1$ dòng tiếp theo, dòng thứ $i$ chứa hai số $u, v$ là có đường di chuyển trực tiếp giữa hai thùng đồ chơi $u$ và $v$.\r\n\r\n#### Output\r\n- Gồm $N$ dòng, dòng thứ $i$ chứa số nguyên dương duy nhất là kết quả $Sum(i)$.\r\n\r\n#### Scoring\r\n+ Trong tất cả các test, $1 \\leq C_i \\leq 10^5$ với $1 \\leq i \\leq N$.\r\n+ Có $5$ subtasks:\r\n+ Subtask $1$ ($10\\%$ số điểm): $N \\leq 3.10^2$.\r\n+ Subtask $2$ ($18\\%$ số điểm): $N \\leq 5.10^3$.\r\n+ Subtask $3$ ($12\\%$ số điểm): $N \\leq 10^5$, mọi thùng đều chứa cùng một loại đồ chơi.\r\n+ Subtask $4$ ($24\\%$ số điểm): $N \\leq 10^5$, không tồn tại hai thùng khác nhau đều chứa cùng loại.\r\n+ Subtask $5$ ($36\\%$ số điểm): $N \\leq 10^5$.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        1 2 3 2 1\r\n        1 2\r\n        1 4\r\n        2 3\r\n        2 5 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        10\r\n        9\r\n        12\r\n        10\r\n        10\r\n        ```","points":500.0,"partial":true,"time_limit":1.2,"memory_limit":262144,"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}}