Can someone tell me how to approach this type of Question…!!
Question contest link
Input graph is a tree (means it is without loops). So my idea was next. For each edge count number of paths (NP) that are go through it.
You need traverse tree up from leaves to parents and save to each parent node number of children (NC). While passing each edge during this process we can calculate NP=NC*(N-NC). Process will be finished in tree center)
The second part of solution is to find minimum reduction itself by making the most valuable reduction each time (max(Wi*(NPi - NPi/2))). We can use binary heap here to succeed in reasonable time
what do mean by this??
Sorry, that was wrong expression. It should look like this
max(NPi*(Wi-floor(Wi/2)))
where
NPi - number of paths that go through i-th edge
Wi - weight of i-th edge
(Wi-floor(Wi/2)) - i-th edge reduction delta
NPi*(Wi-floor(Wi/2)) - total sum S delta at some step of reduction process (in fact, we have to maximize this value at every single step)
thankYou for helping me!!