Hi all, I have been trying to solve this problem from CF #446: http://mirror.codeforces.com/contest/891/problem/C . The editorial description of this problem is very bare bones ( atleast that is what I feel) and and after numerous hours looking at comments and other submissions, I have failed to come up with a solution that works. Can anybody please provide a brief procedure on how to go about solving this problem? Thanks in advance.
And if this is not the way to ask for help here, I apologize as I am quite new to codeforces.
Since MST's are created from the smallest edge weights, if an MST contains edges with weight X, it must also contain all edges with weights less than X (as long as the edges with lesser weights don't form cycles).
For each query, we group the edges in the query by the weights. For each edge group, if the edges in that group form a cycle with all other edges with lesser weights, then the answer to the corresponding query is no, because MST's don't have cycles. If none of the edge groups form cycles, then the answer to the query is yes.
To do this efficiently, we have to sort the edge groups by weight and process the edge groups starting from the lower ones, while maintaining disjoint sets for nodes connected by edges with lower weights. For each edge group, we can just add the edges to the disjoint sets (union) to test for cycles.
However, for the same weight, there might be multiple edge groups, and after testing if an edge group forms a cycle, we need to remove those edges to test the next edge group. I used persistent disjoint sets to account for this.
"For each edge group, if the edges in that group form a cycle with all other edges with lesser weights.." why do we have to check with ALL the edges with lower weights? because a MST may not contain all the edges right?
We add as many lower edges as we can, like how we create an MST with Kruskal. The choice of the edges doesn't matter as it doesn't change which nodes are connected to each other.
Okay I'll try it out. Thank you very much