MMCUT - Tree cut
You are given a tree (a connected, acyclic graph) along with a set of commodities, i.e. pairs of vertices, (s1,t1),...,(sm ,tm) (si ≠ ti). A multicut is a set of edges that when removed disconnects si from ti for all i. There is a unique path Pu,v between every pair of vertices u,v in a tree, and the max-cost of a multicut S is maxi |S ∩ Psi, ti|. You will be given a rooted tree of height 1 and a set of commodities and must return the minimum possible max-cost over all multicuts.
Input
The first line of the input is "N M" (1 ≤ N, M ≤ 100000), where N is the number of vertices in the tree and M is the number of commodities. All vertices are numbered 0, ...,N-1, and the root has label N - 1. M lines then follow, where the ith line is "si ti", representing a commodity (si, ti) where si ≠ ti. Commodities are distinct: neither (si, ti) = (sj, tj) nor (si, ti) = (tj, sj) will hold when i ≠ j.
Output
Your output should consist of a single number, the minimum possible max-cost of a multicut, followed by a newline.
Example
Input: 10 2 0 5 4 8 Output: 1
Added by: | Minilek |
Date: | 2007-10-25 |
Time limit: | 7.601s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | MIT Individual Contest 2007 |