{"code":"olp3g","name":"Đặc trưng của cây (OLP MT&TN 2022 CT)","description":"Khi nghiên cứu về lý thuyết đồ thị, Thuận đã tìm ra một đặc trưng cho cây. Cụ thể, với cây\r\ngồm $n$ đỉnh, đỉnh $i (1 \\le i \\le n)$ có trọng số là $w[i]$, gọi $f(i, j)$ là độ mất cân bằng giữa hai\r\nđỉnh $i$ và $j (1 \\le i, j \\le n)$, trọng số $f(i, j)$ được tính bằng chênh lệnh trọng số giữa đỉnh có\r\ntrọng số lớn nhất với đỉnh có trọng số bé nhất trong các đỉnh nằm trên đường đi từ $i$ đến $j$\r\n(bao gồm cả $i, j$). Độ mất cân bằng $T$ của cây là tổng độ mất cân bằng giữa mọi cặp đỉnh.\r\n\r\n$$T = \\sum_{i=1}^{n} \\sum_{j=1}^{n}f(i, j)$$\r\n\r\n**Yêu cầu:** Cho một cây và trọng số các đỉnh, hãy tính giá trị $T$.\r\n\r\n

Input

\r\n\r\nVào từ thiết bị vào chuẩn có khuôn dạng:\r\n- Dòng đầu chứa số nguyên dương $n$;\r\n- Dòng thứ hai gồm $n$ số nguyên $w_1, w_2, ..., w_n (1 \\le w_i \\le 10^6)$;\r\n- Dòng thứ $k (1 \\le k \\le n - 1)$ trong $n - 1$ dòng tiếp theo chứa hai số $u_k, v_k (1 \\le u_k, v_k \\le n)$\r\nmô tả cạnh thứ $k$ của cây.\r\n\r\n

Output

\r\n\r\n- Ghi ra thiết bị ra chuẩn một số nguyên là giá trị $T$ tính được.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($20\\%$ số điểm): $n \\le 700$;\r\n- Subtask $2$ ($20\\%$ số điểm): $n \\le 7000$;\r\n- Subtask $3$ ($20\\%$ số điểm): $1 \\le w_i \\le 2$;\r\n- Subtask $4$ ($20\\%$ số điểm): $n \\le 10^5$;\r\n- Subtask $5$ ($20\\%$ số điểm): $n \\le 10^6$;\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4\r\n 1 1 2 3\r\n 1 2\r\n 1 3\r\n 1 4\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 8\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4\r\n 1 2 2 2\r\n 1 2\r\n 2 3\r\n 3 4\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 3\r\n ```","points":400.0,"partial":false,"time_limit":2.0,"memory_limit":524288,"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}}