{"problem":{"name":"G. TeddyBearsDay","description":{"content":"You are given the description of TeddyLand, an undirected tree of $n$ nodes where each node represent a TeddyCity, and there's a TeddyPerson that lives in each of the TeddyCities. As everyone knows, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10196G"},"statements":[{"statement_type":"Markdown","content":"You are given the description of TeddyLand, an undirected tree of $n$ nodes where each node represent a TeddyCity, and there's a TeddyPerson that lives in each of the TeddyCities.\n\nAs everyone knows, since the TeddyBearsDay is approaching, people from all around TeddyLand are planning to send TeddyBears to each other.\n\nBut we all know that the TeddyDelivery is very expensive these days (the TeddyCost to send a TeddyBear from a TeddyCity to another TeddyCity is the length of the TeddyPath between them!). \n\nSo you, the TeddyKing, will rearrange the TeddyDeliveries in such a way that each TeddySender will still send the same amount of TeddyBears, and each TeddyReceiver will still receive the same amount of TeddyBears, and the total TeddyCost is minimum.\n\nThe first line will contain one integer $T$ $(1 <= T <= 250)$ - the number of TeddyTestCases.\n\nThe first line of each TeddyCase will contain one integer $n$ $(1 <= n <= 10000)$ - the number of TeddyCities in TeddyLand.\n\nThe following $n -1$ lines will contain three integers each $u_i$ , $v_i$ and $w_i$ $(1 <= u_i, v_i <= n)$ $(1 <= w_i <= 10000)$ - meaning that TeddyCity $u_i$ is connected to TeddyCity $v_i$ with a TeddyRoad of length $w_i$.\n\nThe next line will contain one integer $q$ $(1 <= q <= 10000)$ - the number of TeddyDeliveries planned.\n\nThe following $q$ lines will contain two integers each $u_i$ , $v_i$ $(1 <= u_i, v_i <= n)$ - meaning that the TeddyPerson in TeddyCity $u_i$ wants to send a TeddyBear for the TeddyPerson that lives in the TeddyCity $v_i$. \n\nIt's possible that $u_i$ is equal to $v_i$.\n\nThe total sum of $n <= 5 * 10^5$ \n\nThe total sum of $q <= 5 * 10^5$ \n\nFor each test case, output a single line with the minimum total TeddyCost of all TeddyDeliveries after rearrangement.\n\n## Input\n\nThe first line will contain one integer $T$ $(1 <= T <= 250)$ - the number of TeddyTestCases.The first line of each TeddyCase will contain one integer $n$ $(1 <= n <= 10000)$ - the number of TeddyCities in TeddyLand.The following $n -1$ lines will contain three integers each $u_i$ , $v_i$ and $w_i$ $(1 <= u_i, v_i <= n)$ $(1 <= w_i <= 10000)$ - meaning that TeddyCity $u_i$ is connected to TeddyCity $v_i$ with a TeddyRoad of length $w_i$.The next line will contain one integer $q$ $(1 <= q <= 10000)$ - the number of TeddyDeliveries planned.The following $q$ lines will contain two integers each $u_i$ , $v_i$ $(1 <= u_i, v_i <= n)$ - meaning that the TeddyPerson in TeddyCity $u_i$ wants to send a TeddyBear for the TeddyPerson that lives in the TeddyCity $v_i$. It's possible that $u_i$ is equal to $v_i$.The total sum of $n <= 5 * 10^5$ The total sum of $q <= 5 * 10^5$ \n\n## Output\n\nFor each test case, output a single line with the minimum total TeddyCost of all TeddyDeliveries after rearrangement.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of nodes (TeddyCities).  \n- Let $ G = (V, E) $ be an undirected tree with $ V = \\{1, 2, \\dots, n\\} $, and edge set $ E $, where each edge $ (u_i, v_i) \\in E $ has weight $ w_i \\in \\mathbb{Z}^+ $.  \n- Let $ d(u, v) $ denote the shortest path distance (sum of edge weights) between nodes $ u $ and $ v $ in $ G $.  \n- Let $ q \\in \\mathbb{Z} $ be the number of planned deliveries.  \n- Let $ D = \\{(s_j, t_j) \\mid j \\in \\{1, \\dots, q\\}\\} $ be the multiset of delivery requests, where $ s_j, t_j \\in V $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 250 $  \n2. $ 1 \\le n \\le 10000 $, $ \\sum n \\le 5 \\times 10^5 $  \n3. $ 1 \\le w_i \\le 10000 $  \n4. $ 1 \\le q \\le 10000 $, $ \\sum q \\le 5 \\times 10^5 $  \n5. $ 1 \\le s_j, t_j \\le n $ for all $ j $\n\n**Objective**  \nMinimize the total cost of reassigning deliveries such that:  \n- The number of deliveries originating from each node $ u $ remains unchanged (i.e., the out-degree multiset is preserved).  \n- The number of deliveries received at each node $ v $ remains unchanged (i.e., the in-degree multiset is preserved).  \n\nThat is, let $ f: D \\to D $ be a bijection (rearrangement) such that:  \n- $ |\\{ j \\mid s_j = u \\}| = |\\{ j \\mid f(s_j, t_j) = (u, t') \\}| $ for all $ u \\in V $,  \n- $ |\\{ j \\mid t_j = v \\}| = |\\{ j \\mid f(s_j, t_j) = (s', v) \\}| $ for all $ v \\in V $.  \n\nMinimize:  \n$$\n\\sum_{j=1}^q d(s_j', t_j')\n$$  \nwhere $ f((s_j, t_j)) = (s_j', t_j') $.\n\n**Note**: This is equivalent to finding a minimum-cost bipartite matching between the multiset of senders and receivers, where the cost between sender $ u $ and receiver $ v $ is $ d(u, v) $, and the supply at each node $ u $ equals the number of times $ u $ appears as a source in $ D $, and the demand at each node $ v $ equals the number of times $ v $ appears as a target in $ D $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10196G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}