PROBLEM LINK:
Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic Programming Least Common Ancestor
PROBLEM:
Given a tree with N nodes and M weighted path on the tree, find out the maximum sum of paths such that no paths share any common nodes.
EXPLANATION:
It is easy to find out the states for dynamic programming could be that F[u] denotes the answer inside the subtree rooted at node u. The final answer should be F[1], if we let node 1 be the root of the given tree.
However, it is a little hard to come up with the transitions. We can identify the paths by the least common ancestor (LCA) of the two ends of the path. Therefore, the transitions could be divided into 2 types.
The first one is that we don’t choose any paths whose LCA is at node u. In this case, we can easily sum up all F[v] to update the value of F[u], where v is a child of node u.
The other one is that we do choose a path whose LCA is at node u. Suppose that path is from a—u—b ,where a and b are two ends of this path. Then, we need to sum up the F[v] and plus the weight of this path to update F[u], where v is a child of the any node in the paths u—a and u—b but not on those path.
Directly apply the summation will make the time complexity too high. To make the summation efficient, we introduce another auxiliary array G[], where G[u] is the sum of F[x], where x is a child of node u.
Using the array G, the summation is now the sum of G[v] minus F[v], where v is on the paths u—a and u—b. This summation could be speedup in multiple ways. For example, use the similar double idea of finding LCA. Or you can also try the Segment Tree or Fenwick Tree build on the DFS order of the given tree. Anyway, you can make it in the time of O((M + N)logN).
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.