_Spongey's blog

E — Gardener and Tree, can someone tell me if my approach is wrong?
By _Spongey, history, 12 months ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My approach
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The center being the node with most neighbors? And how do you find how many operations needed?

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No. The center of a tree is the middle node (or middle two nodes) of the longest path of the tree. Check this

        → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are not entirely correct. Check out my submission.

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply