Determine the Maximum Sum of Weights
All submissions for this problem are available.
You are given an undirected tree with n nodes numbered from 1 to n and m weighted tree paths.
If two tree paths share at least one common node, they are forbidden to be selected together, that is, only non-intersecting tree paths are allowed to be selected
Your task is to select a set of tree paths such that the sum of their weights is maximized.
The first line contains an integer T indicating the number of test cases.
For each test case, the first line contains n indicating the number of nodes.
Following n-1 lines describe the tree. Each line contains two integer a, b, which represents an edge between node a and node b.
The next line contains an integer m, the number of the tree paths.
Next m lines contains three integers a, b, c, (a!=b), which represents a tree path from node a to node b and its weight is c.
Output T lines in total. Each line starts with "Case #: " and followed by the maximum sum of weights. Here "#" is the number of the test case starting from 1.
- 1 ≤ T ≤ 10
- 1 ≤ n, m ≤ 100000
- 1 ≤ a, b ≤ n
- 1 ≤ c ≤ 10000
Input: 1 7 1 2 1 3 2 4 2 5 3 6 3 7 3 4 7 10 2 5 6 6 7 5 Output: Case 1: 11
|Tags||acmkgp14, admin, dynamic-programming, fenwick, medium-hard, segment-tree|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions