Pairs of vertices

You are given an undirected, connected graph with $n$ vertices and $n - 1$ edges (i.e., a tree), and an integer $p$ . Every vertex $x$ has an integer value $v_x$ . You must choose $p$ pairs of adjacent vertices such that all $2p$ endpoints are distinct. Your goal is to maximize the sum of the values of the chosen vertices.

Input

Input consists of several cases, each with $n$ , $p$ , $v_1, \dots, v_n$ (vertices are numbered from 1 to $n$ ), and $n - 1$ pairs $x$ $y$ indicating an edge between $x$ and $y$ . Assume $2 \le n \le 10^5$ , $1 \le p \le \lfloor n/2 \rfloor$ , $-10^{-9} \le v_x \le 10^9$ , and that the given edges indeed define a tree.

Output

For each case, if it is impossible to choose exactly $p$ pairs of adjacent vertices, just print “no”. Otherwise, print the largest possible total sum.

Problem information

Author: Salvador Roura
Event: Vint-i-quatrè Concurs de Programació de la UPC - Final
Date: 2026-10-07

Generation: 2026-10-03T14:43:21.705Z