Hey guys, So for this problem, my approach was to like assign every node in the tree a value, which is how long or deep is it. (IDK what it's called but basically if we had a graph: 1 --> 2, 1 --> 3, 2 --> 4. Then the height of 1 is 2, height of 2 is 1, height of 3 and 4 is zero) My code failed on test 2, 25th test. So I was wondering what am I doing wrong (If it got me TLE I was planning to dp the height and just add 1 to it) 240029463 Here's my submission, and also this submission too 240023658
How did you assign height to nodes? In the example you gave, nodes 1 and 2 appear symmetrically the same, so why do they have different heights? (Moreover, your solution is $$$O(n^2)$$$ so it will throw a TLE)
Find the center of the tree. Apply DFS on the center and find for each node how many operations it takes to eliminate that node. Count the number of nodes for which it takes more than $$$K$$$ moves to remove it.
The center being the node with most neighbors? And how do you find how many operations needed?
No. The center of a tree is the middle node (or middle two nodes) of the longest path of the tree. Check this
Alright, thank you pretty much.
Don't know the words but I meant them setting height to them in a differnet array, and for the time complexity I was thinking of solving that by using dp, since the a node's height is the hight of it's child +1
You are not entirely correct. Check out my submission.
Thanks, and can you please review my code, I think I didn't implement my idea correctly (asking so later on I don't implement things wrong thinking my solution is correct)
That's an $$$n^2$$$ solution, my friend. It won't get accepted anyways. I would rather recommend you solve the Tree Algorithms section of CSES.