Ok. Let me explain. I was solving a problem. (I will explain the problem in the next line but if you want to see it, here is the link). You are given a tree. You can assign weights to each node. A good node is a node that has its weight equal to the sum of the weights of its neighbors. You should assign weights in a way such that the number of good nodes is maximized. If there are multiple ways to assign weights and get the maximum number of good nodes then output the one that minimizes the sum of weights of all nodes. This is the problem.
After I read the problem, I quickly came up with a finding that no two neighbors can be good nodes if the graph has more than 2 nodes. My way of thinking was that I should start from the leaf nodes and do some operations. I was thinking only about how to pick the good nodes. I was so convinced that there is a greedy solution and didn't think about other solutions. Like, choose this after choosing this choose that and finally we'll get the best answer. I couldn't solve the problem.
I read the editorial and the solution mentioned there was dp. My first finding was right. But using that, a dp solution is mentioned. My question is when you see a problem, how do you determine that greedy solutions do not work and it has to be solved using dynamic programming?
All answers are welcome and appreciated.
