CF1396E Distance Matching

You are given an integer $ k $ and a tree $ T $ with $ n $ nodes ( $ n $ is even). Let $ dist(u, v) $ be the number of edges on the shortest path from node $ u $ to node $ v $ in $ T $ . Let us define a undirected weighted complete graph $ G = (V, E) $ as following: - $ V = \{x \mid 1 \le x \le n \} $ i.e. the set of integers from $ 1 $ to $ n $ - $ E = \{(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) \} $ i.e. there is an edge between every pair of distinct nodes, the weight being the distance between their respective nodes in $ T $ Your task is simple, find a perfect matching in $ G $ with total edge weight $ k $ $ (1 \le k \le n^2) $ .

N/A

N/A

A tree is a connected acyclic undirected graph. A matching is set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex. A perfect matching is a matching which matches all vertices of the graph; that is, every vertex of the graph is incident to exactly one edge of the matching.