{"problem":{"name":"F. The Lorax","description":{"content":"I am the Lorax, and I speak for the Trees! Plant many of them, plant many now please, We all live in Thneedville, a connected component, that has $n$ nodes and $n -1$ edges this moment, $q$ times ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269F"},"statements":[{"statement_type":"Markdown","content":"I am the Lorax, and I speak for the Trees!\n\nPlant many of them, plant many now please,\n\nWe all live in Thneedville, a connected component,\n\nthat has $n$ nodes and $n -1$ edges this moment,\n\n$q$ times we'll make $x_i$ seeds and the same number of pots,\n\nbut in different places, believe it or nots.\n\nMatch each seed with a pot, and each pot with a seed\n\nBut match in a way that's special indeed:\n\nThe total sum of the distances between every pair\n\nmust be minimized to keep clean the air.\n\nBut if $x_i$ is zero and there is no objection,\n\nwe'd like you to answer the following question:\n\nIf you were to match everything now in the way you've been told\n\nHow many pairs would cross this given road?\n\n**This problem has the same idea, data, and samples (but different flavor-text) as another problem written for a training camp by Travis Meade, and tested by myself. Seems to me to be a notorious coincidence. :)\n\nThe first line will contain a single integer $c$: the number of test cases.\n\nFor each testcase, the first line contains $n$ and $q$: the number nodes in Thneedville, and the number of queries. $n -1$ lines follow, each containing a pair of integers describing the edges in Thneedville.\n\n$q$ lines follow, each of the form $a$ $b$ $x_i$ . If $x_i$ is zero, we are asking about the number of matched pairs that cross the edge from $a$ to $b$ (there will always be an edge directly connecting $a$ to $b$). Otherwise, it indicates that we have created $x_i$ seeds at node $a$, and $x_i$ pots at node $b$.\n\n$c <= 20$\n\n$1 <= n, q <= 10^5$\n\n$1 <= a, b <= n$\n\n$0 <= x_i <= 10^8$\n\nFor each query in which $x_i$ is zero, print a single integer: the number of pairs crossing the queried edge.\n\n## Input\n\nThe first line will contain a single integer $c$: the number of test cases.For each testcase, the first line contains $n$ and $q$: the number nodes in Thneedville, and the number of queries. $n -1$ lines follow, each containing a pair of integers describing the edges in Thneedville.$q$ lines follow, each of the form $a$ $b$ $x_i$ . If $x_i$ is zero, we are asking about the number of matched pairs that cross the edge from $a$ to $b$ (there will always be an edge directly connecting $a$ to $b$). Otherwise, it indicates that we have created $x_i$ seeds at node $a$, and $x_i$ pots at node $b$.$c <= 20$$1 <= n, q <= 10^5$$1 <= a, b <= n$$0 <= x_i <= 10^8$\n\n## Output\n\nFor each query in which $x_i$ is zero, print a single integer: the number of pairs crossing the queried edge.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.  \nLet $ \\mathcal{Q} = \\{(a_i, b_i, x_i) \\mid i \\in \\{1, \\dots, q\\}\\} $ be a sequence of queries.  \n\n**Constraints**  \n1. $ 1 \\le c \\le 20 $  \n2. $ 1 \\le n, q \\le 10^5 $  \n3. For each edge $ (a,b) \\in E $, $ 1 \\le a, b \\le n $  \n4. For each query: $ 0 \\le x_i \\le 10^8 $  \n\n**Objective**  \nFor each query $ (a, b, x_i) $:  \n- If $ x_i > 0 $: add $ x_i $ seeds at node $ a $ and $ x_i $ pots at node $ b $.  \n- If $ x_i = 0 $: compute the number of seed-pot pairs $ (s, p) $ such that the unique path from $ s $ to $ p $ in $ G $ crosses the edge $ (a,b) $, under the optimal matching that minimizes total distance.  \n\n**Key Insight**  \nIn a tree, the optimal matching minimizing total distance pairs seeds and pots such that the number of pairs crossing an edge $ e = (u,v) $ is:  \n$$\n\\min(\\text{seeds on } u\\text{-side}, \\text{pots on } u\\text{-side}) + \\min(\\text{seeds on } v\\text{-side}, \\text{pots on } v\\text{-side})\n$$  \nBut since seeds and pots are added in equal numbers and matched optimally (greedily by subtree balance), the number of pairs crossing edge $ (a,b) $ is:  \n$$\n\\left| S_a - P_a \\right|\n$$  \nwhere $ S_a $ is total seeds on the side of $ a $ (excluding $ b $), and $ P_a $ is total pots on the side of $ a $, **after all updates**.  \n\n**Formal Output for Query $ (a, b, 0) $:**  \nLet $ T_a $ be the connected component containing $ a $ after removing edge $ (a,b) $.  \nLet $ S_a = \\sum_{\\text{seeds added at nodes in } T_a} x_i $,  \n$ P_a = \\sum_{\\text{pots added at nodes in } T_a} x_i $.  \nThen the number of matched pairs crossing $ (a,b) $ is:  \n$$\n\\left| S_a - P_a \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}