{"raw_statement":[{"iden":"statement","content":"More specifically, each circuit design consists of a number of connection points with some connections between them such that the resulting graph is connected and does not have any cycles (i.e., the graph is a tree).\n\nYou are free to place the connection points anywhere on the circuit board and solder the connections between them so that no two connections intersect (except at the connection points). The boards you ordered are fairly large, so there is no danger of running out of space. You can solder so precisely that connections and connection points can be considered infinitesimal.\n\nThis would all be very easy, however your boss persists that each connection needs to be a straight line of length exactly $1 \" mm\"$ (this is, so he says, to make sure the electrons do not have to travel around corners, which would be detrimental to the efficiency of the design).\n\nYou soon realise that battling with him will be unsuccessful. Your quickest way out of this is to etch a new design according to his specifications.\n\nThe input consists of: \n\nIt is guaranteed that these edges describe a valid tree.\n\nOutput $n$ lines, the $i$th of which contains two real numbers $x_i, y_i$, the coordinates of point $i$. To make the production feasible, the following restrictions apply: \n\n"},{"iden":"input","content":"The input consists of:   One line with one integer $n$ ($2 <= n <= 1 thin 000$), the number of connection points. The points are numbered from $1$ to $n$.  $n -1$ lines, each with two integers $a$ and $b$ ($1 <= a, b <= n$), describing a connection between $a$ and $b$. It is guaranteed that these edges describe a valid tree."},{"iden":"output","content":"Output $n$ lines, the $i$th of which contains two real numbers $x_i, y_i$, the coordinates of point $i$. To make the production feasible, the following restrictions apply:   The distance between each pair of points should be at least $10^(-4)$.  The length of each edge should be $1$, up to an #cf_span(class=[tex-font-style-underline], body=[absolute]) error of at most $10^(-6)$.  Edges that are not incident to the same vertex should be at least a distance $10^(-6)$ apart.  The coordinates may not exceed an absolute value of $3 thin 000$.  If there are multiple valid solutions, you may output any one of them."},{"iden":"examples","content":"Input5\n1 2\n1 3\n1 4\n1 5\nOutput0.0000000 0.0000000\n1.0000000 0.0000000\n0.7071068 0.7071068\n0.0000000 1.0000000\n-0.7071068 0.7071068\nInput5\n2 1\n3 1\n2 4\n2 5\nOutput0.0000000 0.0000000\n1.0000000 0.0000000\n-0.7071068 0.7071068\n2.0000000 0.0000000\n1.7071068 0.7071068\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of nations.  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $, where each edge $ (u, v) \\in E $ has weight $ c_{u,v} \\in \\mathbb{Z}^+ $.  \nFor each nation $ i \\in V $, let $ x_i \\in \\mathbb{Z}_{\\geq 0} $ be the initial number of armies, and $ y_i \\in \\mathbb{Z}_{\\geq 0} $ be the required final number of armies.  \nLet $ d_i = x_i - y_i $ be the net surplus (if $ d_i > 0 $) or deficit (if $ d_i < 0 $) of armies at nation $ i $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 250{,}000 $  \n2. $ 1 \\leq c_{u,v} \\leq 10^6 $ for all edges $ (u,v) \\in E $  \n3. $ \\sum_{i=1}^n x_i \\geq \\sum_{i=1}^n y_i $, and $ \\sum_{i=1}^n x_i \\leq 10^6 $  \n4. $ \\sum_{i=1}^n d_i = \\sum_{i=1}^n (x_i - y_i) \\geq 0 $  \n\n**Objective**  \nMinimize the total transportation cost to move armies such that each nation $ i $ ends with at least $ y_i $ armies, where moving $ k $ armies across an edge of cost $ c $ incurs cost $ k \\cdot c $. The movement must respect the tree structure and net surplus/deficit constraints.  \n\nThe minimum cost is the sum over all edges $ (u,v) \\in E $ of $ c_{u,v} \\cdot |f_{u,v}| $, where $ f_{u,v} $ is the net flow of armies across the edge (from the subtree side with surplus to the side with deficit), and the flow is determined by the subtree sum of $ d_i $.","simple_statement":"You have n nations connected by n-1 roads (a tree). Each road has a cost per army. Each nation i has x_i armies currently and needs y_i armies. Move armies between nations using the roads to meet all needs at minimum total cost.","has_page_source":false}