I took part in Samsung SCPC 2017 contest but couldn't manage to solve the last problem about tree in online round 1:

Given an integer and a tree that has M nodes. This tree has exactly 2 * N leaves numbered 1...2 * N (nodes from 2 * N + 1...M are not leaves). Each edge in tree has a weight in [1, 10⁹]. For each set of leaves S that doesn't contain both leaf x and leaf x + N for every , let T(S) be the minimum sub-tree of given tree that has all leaves in S. Among all S, find largest total edge weight of T(S). Examples:
N = 2, M = 5
Edges: (5, 1, 10);(5, 2, 20);(5, 3, 30);(5, 4, 40).
- Answer is 70 and tree with nodes {5, 3, 4} has weight 70.
Edges: (5, 1, 20);(5, 2, 30);(5, 3, 10);(5, 4, 40).
- Answer is 60, tree {5, 1, 4}.
Any idea?