{"problem":{"name":"G. Yet Another Maxflow Problem","description":{"content":"In this problem you will have to deal with a very special network. The network consists of two parts: part _A_ and part _B_. Each part consists of _n_ vertices; _i_\\-th vertex of part _A_ is denoted ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF903G"},"statements":[{"statement_type":"Markdown","content":"In this problem you will have to deal with a very special network.\n\nThe network consists of two parts: part _A_ and part _B_. Each part consists of _n_ vertices; _i_\\-th vertex of part _A_ is denoted as _A__i_, and _i_\\-th vertex of part _B_ is denoted as _B__i_.\n\nFor each index _i_ (1 ≤ _i_ < _n_) there is a directed edge from vertex _A__i_ to vertex _A__i_ + 1, and from _B__i_ to _B__i_ + 1, respectively. Capacities of these edges are given in the input. Also there might be several directed edges going from part _A_ to part _B_ (but never from _B_ to _A_).\n\nYou have to calculate the [maximum flow value](https://en.wikipedia.org/wiki/Maximum_flow_problem) from _A_1 to _B__n_ in this network. Capacities of edges connecting _A__i_ to _A__i_ + 1 might sometimes change, and you also have to maintain the maximum flow value after these changes. Apart from that, the network is fixed (there are no changes in part _B_, no changes of edges going from _A_ to _B_, and no edge insertions or deletions).\n\nTake a look at the example and the notes to understand the structure of the network better.\n\n## Input\n\nThe first line contains three integer numbers _n_, _m_ and _q_ (2 ≤ _n_, _m_ ≤ 2·105, 0 ≤ _q_ ≤ 2·105) — the number of vertices in each part, the number of edges going from _A_ to _B_ and the number of changes, respectively.\n\nThen _n_ - 1 lines follow, _i_\\-th line contains two integers _x__i_ and _y__i_ denoting that the edge from _A__i_ to _A__i_ + 1 has capacity _x__i_ and the edge from _B__i_ to _B__i_ + 1 has capacity _y__i_ (1 ≤ _x__i_, _y__i_ ≤ 109).\n\nThen _m_ lines follow, describing the edges from _A_ to _B_. Each line contains three integers _x_, _y_ and _z_ denoting an edge from _A__x_ to _B__y_ with capacity _z_ (1 ≤ _x_, _y_ ≤ _n_, 1 ≤ _z_ ≤ 109). There might be multiple edges from _A__x_ to _B__y_.\n\nAnd then _q_ lines follow, describing a sequence of changes to the network. _i_\\-th line contains two integers _v__i_ and _w__i_, denoting that the capacity of the edge from _A__v__i_ to _A__v__i_ + 1 is set to _w__i_ (1 ≤ _v__i_ < _n_, 1 ≤ _w__i_ ≤ 109).\n\n## Output\n\nFirstly, print the maximum flow value in the original network. Then print _q_ integers, _i_\\-th of them must be equal to the maximum flow value after _i_\\-th change.\n\n[samples]\n\n## Note\n\nThis is the original network in the example:\n\n<center>![image](https://espresso.codeforces.com/2cde6a73d42b3f76712d52ebfe4f6441bc5dc343.png)</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[samples]\n\n## Note\n\n这是示例中的原始网络：","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, q \\in \\mathbb{Z}^+ $ denote the number of vertices in each part, the number of $ A \\to B $ edges, and the number of updates, respectively.  \nLet $ A = \\{A_1, A_2, \\dots, A_n\\} $ and $ B = \\{B_1, B_2, \\dots, B_n\\} $ be the vertex sets of the two parts.  \n\nFor $ i \\in \\{1, \\dots, n-1\\} $:  \n- Let $ c_{A,i} \\in \\mathbb{R}^+ $ denote the capacity of edge $ A_i \\to A_{i+1} $.  \n- Let $ c_{B,i} \\in \\mathbb{R}^+ $ denote the capacity of edge $ B_i \\to B_{i+1} $.  \n\nLet $ E_{AB} \\subseteq \\{1,\\dots,n\\} \\times \\{1,\\dots,n\\} \\times \\mathbb{R}^+ $ be the multiset of directed edges from $ A $ to $ B $, where each element $ (x, y, z) \\in E_{AB} $ represents an edge $ A_x \\to B_y $ with capacity $ z $.  \n\nLet $ \\mathcal{G} = (V, E) $ be the directed flow network with:  \n- Vertex set $ V = A \\cup B $,  \n- Edge set $ E = \\bigcup_{i=1}^{n-1} \\{ (A_i, A_{i+1}), (B_i, B_{i+1}) \\} \\cup E_{AB} $.  \n\n**Constraints**  \n1. $ 2 \\le n, m \\le 2 \\cdot 10^5 $, $ 0 \\le q \\le 2 \\cdot 10^5 $  \n2. $ 1 \\le c_{A,i}, c_{B,i} \\le 10^9 $ for all $ i \\in \\{1, \\dots, n-1\\} $  \n3. For each $ (x, y, z) \\in E_{AB} $: $ 1 \\le x, y \\le n $, $ 1 \\le z \\le 10^9 $  \n4. Updates: each update sets $ c_{A,v_i} \\leftarrow w_i $ for $ 1 \\le v_i < n $, $ 1 \\le w_i \\le 10^9 $  \n\n**Objective**  \nCompute the maximum flow from $ A_1 $ to $ B_n $ in $ \\mathcal{G} $, and update it after each of the $ q $ capacity changes.  \n\nLet $ f_0 $ be the maximum flow in the initial network.  \nFor each update $ i \\in \\{1, \\dots, q\\} $, let $ f_i $ be the maximum flow after the $ i $-th update.  \n\nOutput $ f_0, f_1, \\dots, f_q $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF903G","tags":["data structures","flows","graphs"],"sample_group":[["4 3 2\n1 2\n3 4\n5 6\n2 2 7\n1 4 8\n4 3 9\n1 100\n2 100","9\n14\n14"]],"created_at":"2026-03-03 11:00:39"}}