{"code":"eztree","name":"Cây dễ","description":"Cho một cây $n$ đỉnh có trọng số, định nghĩa $f(u,v)$ là hiệu giữa trọng số cạnh lớn nhất và nhỏ nhất trên đường đi đơn từ $u$ đến $v$, hay đặt $w_1$ là trọng số cạnh nhỏ nhất trên đường đi từ $u$ đến $v$, $w_2$ là trọng số cạnh lớn nhất trên đường đi từ $u$ đến $v$ thì $f(u,v)=w_2-w_1$.\r\n\r\nCho $q$ truy vấn, mỗi truy vấn đưa ra số nguyên dương $k$ $(k\\leq n)$ và $k$ đỉnh phân biệt $u_1,u_2,...,u_k$ và yêu cầu tính giá trị của $\\sum_{i=1}^{k-1}{\\sum_{j=i+1}^{k}} f(u_i,u_j)$. \r\n\r\nHãy trả lời các truy vấn trên.\r\n\r\n## Input\r\n - Dòng $1$ chứa hai số nguyên dương $n,q$ $(1\\leq n,q \\leq 10^5)$.\r\n - $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u,v,w$ thể hiện cạnh nối trực tiếp giữa $u$ và $v$ có trọng số $w$ trên cây $(1\\leq u,v \\leq n,u\\neq v,1\\leq w\\leq 10^6)$.\r\n - $q$ dòng tiếp theo, mỗi dòng có $k+1$ số nguyên dương lần lượt là $k,u_1,u_2,...,u_k$ cho mỗi truy vấn. Dữ liệu đảm bảo tổng $k$ trong các truy vấn không vượt quá $3\\cdot10^5$.\r\n\r\n## Output\r\n - Gồm $q$ dòng, dòng thứ $i$ chứa một số nguyên dương duy nhất là đáp án cho truy vấn thứ $i$.\r\n\r\n## Scoring\r\n- Subtask $1$ ($10\\%$ số điểm): $n,q\\leq 500$.\r\n- Subtask $2$ ($10\\%$ số điểm): $n,q\\leq 1000$.\r\n- Subtask $3$ ($20\\%$ số điểm): $q=1,n\\leq 10^5$.\r\n- Subtask $4$ ($60\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n## Example\r\n**Sample input**\r\n```\r\n10 3\r\n2 1 7\r\n1 3 12\r\n1 4 12\r\n4 5 11\r\n2 6 12\r\n1 7 8\r\n7 8 11\r\n9 4 4\r\n10 4 2\r\n3 8 10 1 \r\n3 5 3 8 \r\n2 1 2 \r\n\r\n```\r\n**Sample output**\r\n```\r\n23\r\n9\r\n0\r\n```\r\n## Note\r\nGiải thích truy vấn $1$:\r\n - $f(8,10)=12-2=10$.\r\n - $f(8,1)=11-8=3$.\r\n - $f(10,1)=12-2=10$.\r\n\r\nĐáp số là $10+3+10=23$.\r\n\r\n![enter image description here][1]\r\n\r\n\r\n  [1]: https://cdn.lqdoj.edu.vn/media/pagedown-uploads/note.png","points":2400.0,"partial":true,"time_limit":0.69,"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}}