PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Hard PREREQUISITES:trees, max flow, bipartite graphs. PROBLEM:There is a country with N cities. Road network in the country can be represented as a tree. There are two companies A and B. A and B wants to build M1 and M2 paths respectively. A path is a collection of one or more roads. For building a path, the company will be given a profit amount. You have to select subsets of paths from A and B in such a way that there should not be two paths of different companies intersecting each other. Note that paths of same company might intersect each other. Find out maximum possible amount of profit that the companies can have. QUICK EXPLANATION
EXPLANATIONHow to check whether two paths intersect or not? Let us have a look at the following image. Now let us say that we have two paths (s1, t1) and (s2, t2). We want to find whether they intersect or not?
Now our problem reduces to how to detect whether a vertex lies on the given path or not. There can be two cases. Case 2: p lies on one of the paths from s to lca(s, t) or t to lca(s, t). How to find lca of a tree Trivial algorithm for finding LCA can take time of height of the tree, which can go of O(N) in the worst case. Please have a look at this amazing topcoder tutorial which discusses the problem in great detail and proposes many solutions. Finding weighted independent set in a bipartite graphGraph Construction Now you can realize that answer of our problem is finding the maximum weighted independent set of the graph. Maximum weighted independent set of a graph is collection of vertices having maximum weight and no two vertices in the set have an edge between them. Network construction Our network will have 4 parts. source, sink, and parts corresponding to A and B. Call the part corresponding to A left and that of B right.
Please see the following image for more clarification.
Claim Proof of the construction Minimal cut denotes the minimal total sum of deleted edges' costs whose deletion will cause source and sink to nolonger have a route between them. Note that when we find the minimal cut, we will never delete the edges between left and right part, because their capacity (or the weight in the mincut problem) is infinity. Instead it will be better even to delete all the edges from the source to the left part, because the sum of the finite number of finite numbers is less that infinity. What does path the path here?
Let us consider a path in the flow diagram. We have already noted that intermediate edges will never be deleted. Having that given, we need to make sure that if there is a pair of edges (denote it by (A, B) where A is the edge of the first company (source to left) and B is the edge of the second company(right to sink)), we need to ensure that there is an intermediate edge between them because then at least one  A or B is deleted, if there is a construction A > intermediate edge > B then A and B can not live together. In the beginning of the construction of the network, we were adding such edges in case A's and B's corresponding routes intersect. But what is more, As long as there is such a combination, there is a route between the source and the destination/sink and vice versa. So now we conclude that we need to delete some edges in such a way that there will not be a way from the source to the sink in the constructed network. This is a minimal cut problem and as noted in the starting, it is widely known that this weight equals to the maximal flow. So finally what is the answer of our problem? We need to delete edges with the minimal total cost. If we delete edges with the total cost C, SumAllCosts  C will be the answer. So the answer is: The total sum of edges' costs  Maximal flow in the network built. Complexity: Here N * log n corresponds to time taken in detecting intersection of the paths. To fit the solution in time, faster implementation of the max flow were required, Dinic algorithm can get TLE, safe way to solve the problem is to use Push Relabel Algorithm. HOMEWORK
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 Jun '14, 15:01

When I first read the problem I thought that maybe there is a more specific algorithm for finding the maximum weighted independent set in the bipartite graph, given that the bipartite graph is not arbitrary  it is the intersection graph of two sets of paths in a tree. For instance, the following problem has a much better solution. If you have a single set of paths in the tree and you generate the graph of their intersections, you can find the maximum weight independent set of this graph in polynomial time (whereas you cannot find it in polynomial time in a general graph). Such graphs are called chordal graphs. Thus, the graph from the problem is a kind of chordal bipartite graph, so I thought that maybe there is some special algorithm for it which is more efficient than using maxflow. I thought about it and I couldn't find one, but it would have been nice if one existed. answered 16 Jun '14, 21:31

I don't think there's any point to making data that needs faster flow algorithms than FordFulkerson. They're so rarely required in competitions where you can't use prewritten code that there's no point in trying to implement them, it's simpler to just use a code from somewhere else and source it. answered 17 Jun '14, 02:37

I implemented FordFulkerson with a mix of BFS (EdmondsKarp) and DFS augmentation. I do DFS on the first (M1+M2)/2 augmentations, and BFS afterwards. Also, I try a different order of nodes to visit per augmentation, so I expect to usually get short augmenting paths. This got accepted. I know this shouldn't pass the time limit, but I guess it's really hard to generate max flow cases to break such solutions, especially if our graph is bipartite with a specific structure (as mugurelionut explains). The submission: http://www.codechef.com/viewplaintext/4097453 answered 16 Jun '14, 23:40
The idea of using DFS augmentation for finding first V/2 augmented path and then using BFS augmentation is really nice!
(17 Jun '14, 01:34)

Can't you explain please this part of Author's solution for(i = 2; i < n; i++) { lift(i);//< If I am not mistaken you must lift if the excess is positive but here you don't know whether the excess is positive or not. And you will not find such k for which if (fc[k][a[k][i]] > 0 && h[a[k][i]] + 1 < h[k]) h[k] = h[a[k][i]] + 1; and h[k] = n + n; will stay n+n and later you will not be able to push flow to vertex k. Where am I wrong ? Thanks! answered 16 Jun '14, 17:53

I,too, don't understand the following part "If the vertex p lies on the path (s, t) then lca(t, p) should be t and lca(s, p) should be s. If p does not lie on the path, then both the conditions can not be true simultaneously.". For, if we choose p=lca(s,t) then the above formula gives "lca(t,p) = p = t = s = lca(s,p" answered 17 Jun '14, 02:26

Just a little note on the cross function implemented in author's solutions: most of the conditionals are useless there. If a path intersects the other, you can test just if lca 1 is between (s1,t1) or if lca 2 is between (s2,t2). The simplified version of the cross function is as follows:
answered 19 Jun '14, 07:39

@dpraveen sir am not getting the image :(
The tag "mincostflow" is wrong. It should be max flow.
pictures are missing. please fix it.
@akulsareen: fixed, ty for informing and sorry for being late :(
@1smll: the tag is corrected now. Thanks for point iit out.