Hello guys
I was trying to solve problem E from last CF round and I got the idea that we can make a bridge tree(compress unbridged-connected nodes into a single node) and then find the diameter of the tree.
I saw some solutions that first find the nodes and compress them and then new dfs to find diameter as usual but I saw the shortest codes submitted and was amazed to see that it just contained a single dfs and was very neat.
I have two questions. Firstly how does this code work without actually finding diameter and how do people come up with such implementation? Do they first think about the whole implementation which is shortest and then code?
I think this is how that code works:
Basically, instead of calculating the width in the compressed tree, you can just calculate the width in the dfs tree.
Consider the tree formed by the dfs that finds the bridges.
In the dfs tree, let DP[x] be the highest amount of bridges on a path down from X to a leaf in the tree.
At each node X, let F_X(Y) = DP[Y] + IS_BRIDGE(X, Y). We find two children A' and B' with maximum F_X, and get the offer F_X(A') + F_X(B'). If there is only one child A', we get the offer F_X(A'). Our answer is the maximum of these offers.
Clearly we can never get an offer higher than the correct answer to the case.
Now, let the optimal path be from A to B. Let C = lca(A, B)in the dfs tree.
The main thing here is that any simple path from C to A has the same amount of bridges, and vice versa for C and B. Therefore we can just use the paths in the DFS tree.
We have two cases:
In case 1, in node C, we have the offer F_C(B'). In case 2, in node C, we have the offer is F_C(A') + F_C(B'). Either way, we get the correct answer.
Hi, I first tried to make a bridge tree, too! but after about 1 hour thinking about how to code it short and good, I reached to some good things... one of this: Suppose that you call dfs at the first time and your root is vertex 1. if you remove vertex 1, the graph will become to some disjointed components. and NO EDGE can be between two different components (because if there be an edge between them in the real graph, then these two components have to be connected because with calling any vertex in this components, all of the vertexes in this two components will be marked and they became to one component, not two). so the edges are just between two vertexes u and v if and only if u is one of the vertexes in the path between v and root or vise versa. and as you know, we should merge vertexes in one cycle into one vertex, and then count the edges. Long story short, we use dp-dfs and this is too much easier for us to find the answer, cause of the fact about edges, and the rest is history :) and about how people come up with this implementation, I have to told you all of this is just for experience is coding and solving a lots of problems with this idea. Coding is something that you can just grow up in it just with coding more and don't settle :) Sorry for my weak english, and wish that you see the light! If you had any other question just ask. Wish you the bests!