CLTRTS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Soumik Sarkar
Tester: Subham Das
Editorialist: Soumik Sarkar

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graphs, depth first search

PROBLEM:

Given a tree of N vertices each with weight wi, find for each vertex the weight of the path which has maximum sum of weights of vertices along it out of all paths that start at that vertex.

EXPLANATION

Let us discuss the naive approach first, which involves running a search (BFS/DFS) from each vertex and calculating the answers one by one.

def dfs(u, parent):
    maxval = 0
    for v in neighbours[u]:
        if v!=parent:
            maxval = max(maxval, dfs(v, u))
    return maxval + w[u]

Calling this function for a vertex u calculates the answer for that vertex. Repeating this for each vertex will give us all the required values, but this is too slow. Notice that when we calculate the answer for one vertex, we are discarding a lot of important information gathered. We are only taking the return value for the vertex we started the dfs with, and not bothering about the values gathered by the other vertices. Let’s see how we can use these.

For simplicity, let’s call the path with largest sum of weights (as required by the question) the best path, and the sum of weights of all vertices on this path as the weight of the best path.

Let us pick an arbitrary vertex as our root. Now we will run a dfs just like above. Notice that the return value of dfs(v, u) is the weight of the best path if we go from u into the subtree rooted at v. Surely the overall best path for u is the the maximum of all such best paths into each of its neighbours.

Observation 1: After a dfs call to any vertex u, the vertex u knows the weights of all the such best paths into each of its neighbours’ subtrees, except the parent subtree of u. (The term parent subtree here refers to the subtree rooted at the parent of u if u is considered the root of the entire tree.)
Observation 2: The initial root is the only vertex for which above statement does not hold, since it has no parent. For the root, the answer is known at the end of the dfs.

As each vertex (except the root) is only one value away from the answer, and as this value is associated with the parent, we will run another dfs from our initial root and push down these required values to each vertex. In other words, dfs2(u, parent, parentval) will push down parentval from parent to u such that parentval equals dfs(parent, u).

In dfs2, starting at the root, we calculate the maximum of all best paths into neighbours from the current vertex u as maxval and the neighbour for which the maximum was obtained as maxnbr. Now maxval + w[u] is the answer for vertex u, which we can save as ans[u].
For each of its neighbours v, we will recursively call dfs2 with parentval equal to ans[u], except for the neighbour maxnbr. For the special maxnbr we need to calculate the maximum of all paths into all neighbours of u as before, but this time excluding maxnbr, and send this value + w[i] as parentval.

We require 2 separate dfs procedures for the solution so the complexity is \mathcal{O}(n). For better understanding refer to the author’s solution.

AUTHOR’S SOLUTION:

Author’s solution can be found here.

1 Like