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!!