{"problem":{"name":"E. Longest path Problem","description":{"content":"You are given a weighted undirected connected tree that contains n nodes and n - 1 edges. every edge has a weight and there is exactly one path between every pair of different nodes. Now you should ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10226E"},"statements":[{"statement_type":"Markdown","content":"You are given a weighted undirected connected tree that contains n nodes and n - 1 edges.\n\nevery edge has a weight and there is exactly one path between every pair of different nodes.\n\nNow you should take each edge independently and do the following : \n\n1.remove the edge from tree (that will divide the tree into two components).\n\n2.reconnect the edge again in which it is still a connected tree (every end of the edge should be connected to a node from a different component).\n\nYou should do this so that the longest path in the tree is minimised. \n\nFirst line contains one integer n (2 ≤ n ≤ 200000)\n\nThe next n - 1 lines will contain 3 integers for each,u v w (1 ≤ u, v ≤ n) (1 ≤ w ≤ 109), which means that there is an edge of weight w connecting the nodes u and v.\n\nit is guaranteed that the edges describes one connected tree.\n\nyou should print n - 1 lines, the ith line should be the answer for the ith edge.\n\nThe sample graph \n\nSolution for the second edge: after removing the second edge, add it to again between Node 2 and Node 3\n\n## Input\n\nFirst line contains one integer n (2 ≤ n ≤ 200000)The next n - 1 lines will contain 3 integers for each,u v w (1 ≤ u, v ≤ n) (1 ≤ w ≤ 109), which means that there is an edge of weight w connecting the nodes u and v.it is guaranteed that the edges describes one connected tree.\n\n## Output\n\nyou should print n - 1 lines, the ith line should be the answer for the ith edge.\n\n[samples]\n\n## Note\n\nThe sample graph Solution for the second edge: after removing the second edge, add it to again between Node 2 and Node 3","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ L \\in \\mathbb{Z} $ be the number of levels.  \nFor each level $ \\ell \\in \\{1, \\dots, L\\} $, let $ R_\\ell = \\{(r_{\\ell,1}, c_{\\ell,1}), (r_{\\ell,2}, c_{\\ell,2}), (r_{\\ell,3}, c_{\\ell,3}), (r_{\\ell,4}, c_{\\ell,4})\\} $ be the set of initial positions of four distinct robots on a 12×12 grid, where no cell is blocked.\n\n**Constraints**  \n1. $ 1 \\leq L \\leq 1000 $  \n2. For each $ \\ell $, $ 1 \\leq r_{\\ell,i}, c_{\\ell,i} \\leq 12 $ for all $ i \\in \\{1,2,3,4\\} $  \n3. All four robot positions in each level are distinct and lie on non-blocked cells.  \n\n**Objective**  \nFind a sequence of at most 1000 moves (each move being a direction: up, down, left, or right) such that, after applying all moves in order, **all four robots simultaneously end on crossed cells**, under the following movement rules:  \n- All four robots attempt to move in the same direction simultaneously.  \n- A robot moves if and only if:  \n  - Its target cell is not blocked, **and**  \n  - Either the target cell is empty or crossed, **or**  \n  - The target cell contains another robot that is itself moving (i.e., that robot’s move is not blocked).  \n- If a robot is blocked from moving, it remains in place.  \n- A robot successfully reaches a crossed cell if and only if it ends its movement on a cell marked as crossed.  \n\n**Output**  \nFor each level $ \\ell $, output a sequence of moves (as strings: \"U\", \"D\", \"L\", \"R\") of length ≤ 1000 that achieves the objective.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10226E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}