{"code":"langla","name":"Làng Lá","description":"Sau khi bị **pain** hack pay làng thì làng lá hiện đang trong công cuộc xây dựng lại. Hôm nay **Uzumaki** [user:bin9638], hokage của làng lá và **Uchiha** [user:algorit], người còn lại cuối cùng của tộc **Uchiha** đang lên kế hoạch xây dựng lại làng. Ngôi làng gồm $n$ ngôi nhà được đánh số từ $1$ tới $n$ $(n \\le  2*10^5)$ và có $n-1$ con đường nối $2$ ngôi nhà bất kì sao cho tất của các nhà đều được liên thông với nhau, mỗi con đường sẽ có độ dài $w$ $(w \\le  10^9)$.\r\n\r\n\r\nNgôi làng bây giờ có $q$ $(q \\le  2*10^5)$  bộ ba ngôi nhà wibu. Với mỗi bộ ba ngôi nhà này [user:bin9638] và [user:algorit] muốn tính giá trị nhỏ nhất của $wibu(a,x)+wibu(b,x)+wibu(c,x)$ với $wibu(u,v)$ là khoảng cách để đi từ nhà $u$ đến nhà $v$. Ở đây $x$ là $1$ ngôi nhà bất kì trong làng.\r\n\r\n<h4>Input</h4>\r\n\r\n+ Dòng đầu tiên là số $n$.\r\n+ $n-1$ dòng tiếp theo mỗi dòng là $3$ số $u, v, w$ biểu thị có đường nối $2$ nhà $u$ và $v$ với độ dài $w$.\r\n+ Dòng tiếp theo là số $q$.\r\n+ $q$ dòng tiếp theo là các truy vấn, mỗi truy vấn gồm $3$ số $a,b,c$.\r\n\r\n<h4>Output</h4>\r\n\r\n- Gồm $q$ dòng là kết quả cho các truy vấn.\r\n\r\n<h4>Scoring</h4>\r\n\r\n+ Subtask $1$ ($30\\%$ số điểm): $n , q \\le  15$\r\n+ Subtask $2$ ($30\\%$ số điểm): $n , q \\le  1000$\r\n+ Subtask $3$ ($40\\%$ số điểm): $n , q \\le  2*10^5$\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        4\r\n        1 2 1\r\n        2 3 2\r\n        1 4 3\r\n        2\r\n        1 2 3 \r\n        1 2 4 \r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        3\r\n        4\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        + Ngôi làng có sơ đồ:   \r\n        ```\r\n                                  1\r\n                             (1) / \\(3)\r\n                                /   \\\r\n                               2     4\r\n                         (2)  /\r\n                             /\r\n                            3\r\n        ```\r\n        + Ở truy vấn $1$ ngôi nhà $x$ là nhà $2$, kết quả sẽ là $3$.\r\n        + Ở truy vấn $2$ ngôi nhà $x$ là nhà $1$, kết quả sẽ là $4$.","points":1700.0,"partial":true,"time_limit":1.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}}