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₁, …, v_(n) (vertices
are numbered from 1 to n), and n − 1 pairs x y indicating an edge
between x and y. Assume 2 ≤ n ≤ 10⁵, 1 ≤ p ≤ ⌊n/2⌋, −10⁻⁹ ≤ v_(x) ≤ 10⁹,
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

© Jutge.org, 2006–2026.
https://jutge.org
