For the first subtask, it suffices to brute force all ~2^N~ possible choices of nodes to cut. For each choice, check to see if the remaining nodes are connected and if their sum falls within the range ~[K,2K]~.

Time complexity: ~\mathcal{O}(N2^N)~

For the second subtask, we root the tree arbitrarily and we perform dynamic programming on the different subtrees. Our dp state records whether there exists a subtree of weight exactly ~W~ rooted at ~x~ for all ~W~ in ~[1,2K]~. The state transitions consist of iterating through all children of ~x~ and adding their values to ~x~'s dp in the same way as knapsack dp is performed. Since each state is either ~0~ or ~1~, we store it inside a bitset. This allows us to perform state transitions using bit operations in ~\mathcal{O}(\frac{N}{B})~ where ~B~ is the bitset constant (usually ~B = 64~).

Time complexity: ~\mathcal{O}(\frac{N^3}{B})~

For the final subtask, we first remove all nodes with weight ~> 2K~ as they clearly cannot be part of our answer. If there is a node with weight in the range ~[K,2K]~, we can use it as our answer and we are done. Otherwise, all remaining nodes have weight ~<K~. We can then run a BFS/DFS on each connected component and add nodes to our answer until the total weight is ~\ge K~. If our current total is ~W~ and ~W<K~, we know that ~W+w \le 2K~ since the weight of any single node is ~w<K~. Therefore, this algorithm will find an answer if the total weight of any connected component is ~\ge K~. If this is not the case, the answer doesn't exist which shows that the algorithm is correct.

Time complexity: ~\mathcal{O}(N)~