{"problem":{"name":"Select Edges","description":{"content":"You are given a tree with $N$ vertices. For each $i = 1, 2, \\ldots, N-1$, the $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$ and has a weight $w_i$. Consider choosing some of the $N-1$ edges (pos","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc259_f"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices. For each $i = 1, 2, \\ldots, N-1$, the $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$ and has a weight $w_i$.\nConsider choosing some of the $N-1$ edges (possibly none or all). Here, for each $i = 1, 2, \\ldots, N$, one may choose at most $d_i$ edges incident to Vertex $i$. Find the maximum possible total weight of the chosen edges.\n\n## Constraints\n\n*   $2 \\leq N \\leq 3 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   $-10^9 \\leq w_i \\leq 10^9$\n*   $d_i$ is a non-negative integer not exceeding the degree of Vertex $i$.\n*   The given graph is a tree.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$d_1$ $d_2$ $\\ldots$ $d_N$\n$u_1$ $v_1$ $w_1$\n$u_2$ $v_2$ $w_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$ $w_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc259_f","tags":[],"sample_group":[["7\n1 2 1 0 2 1 1\n1 2 8\n2 3 9\n2 4 10\n2 5 -3\n5 6 8\n5 7 3","28\n\nIf you choose the $1$\\-st, $2$\\-nd, $5$\\-th, and $6$\\-th edges, the total weight of those edges is $8 + 9 + 8 + 3 = 28$. This is the maximum possible."],["20\n0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2\n4 9 583\n4 6 -431\n5 9 325\n17 6 131\n17 2 -520\n2 16 696\n5 7 662\n17 15 845\n7 8 307\n13 7 849\n9 19 242\n20 6 909\n7 11 -775\n17 18 557\n14 20 95\n18 10 646\n4 3 -168\n1 3 -917\n11 12 30","2184"]],"created_at":"2026-03-03 11:01:14"}}