{"problem":{"name":"Make Biconnected","description":{"content":"You are given an undirected tree $G$ with $N$ vertices. **The degree of every vertex in $G$ is at most $3$.**   The vertices are numbered $1$ to $N$. The edges are numbered $1$ to $N-1$, and edge $i$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc160_e"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected tree $G$ with $N$ vertices. **The degree of every vertex in $G$ is at most $3$.**  \nThe vertices are numbered $1$ to $N$. The edges are numbered $1$ to $N-1$, and edge $i$ connects vertex $u_i$ and vertex $v_i$.  \nEach vertex has a fixed weight, and the weight of vertex $i$ is $W_i$.\nYou will add zero or more edges to $G$. The cost of adding an edge between vertex $i$ and vertex $j$ is $W_i + W_j$.\nPrint one way to add edges to satisfy the following condition for the minimum possible total cost.\n\n*   $G$ is $2$\\-vertex-connected. In other words, for every vertex $v$ in $G$, removing $v$ and its incident edges from $G$ would not disconnect $G$.\n\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $3 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is a tree.\n*   The degree of every vertex in the given graph is at most $3$.\n*   $1 \\leq W_i \\leq 10^9$\n*   $W_i$ is an integer.\n*   The sum of $N$ across the test cases is at most $2 \\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format, where $\\mathrm{case}_i$ represents the $i$\\-th test case:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_N$\n\nEach test case is in the following format:\n\n$N$ \n$W_1$ $W_2$ $\\dots$ $W_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc160_e","tags":[],"sample_group":[["2\n3\n2 3 5\n1 2\n2 3\n7\n1 10 100 1000 10000 100000 1000000\n1 2\n2 3\n2 4\n3 5\n3 6\n4 7","1\n1 3\n2\n7 6\n1 5\n\nIn the first test case, adding an edge connecting vertex $1$ and vertex $3$ makes $G$ satisfy the condition in the problem statement.  \nThe cost of this is $W_1 + W_3 = 2 + 5 = 7$. There is no way to add edges to satisfy the condition for a cost of less than $7$, so this is a valid solution.\nIn the second test case, the solution above has a total cost of $(W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001$, which is the minimum possible."]],"created_at":"2026-03-03 11:01:14"}}