Learned a lot.
In this blog I would like to put emphasis on what I learned from other’s implementation. The idea is quite simple: for every edge E find the maximum number that appears in the paths that contain E and set that number for E, then check if there’s a contradiction. However, the implementation seems to be not easy.
I want to talk about two techniques in this code.
The first one is how to find the index of the edge that we are visiting.
Instead of using map<pair<int,int>,int> the author uses the lower vertex of each edge to denote that edge and label them when doing the DFS. This reduces both time and space complexity.
The second one is how to find the path between two vertices.
In a rooted tree, we can find the path by finding the LCA of the two vertices. The algorithm is quite naive: jump up over and over until the two vertices meet. The author uses very short codes to achieve this:
while (u != v) {
if (dep[u] < dep[v]) swap(u, v);
//do something...
u = fa[u];
}Overall, the question is good and what I learned is also amazing which I think is worth writing a blog.