Блог пользователя HexShift

Автор HexShift, история, 14 месяцев назад, По-английски

Do you personally prefer tree problem with $$$N-1$$$ pair of integers input where $$$i^{th}$$$ input ($$$u_i$$$ and $$$v_i$$$) denotes the nodes that $$$i^{th}$$$ edge connects and all the edges guarantee a tree, or $$$N-1$$$ integers input where $$$i^{th}$$$ input ($$$p_i$$$) indicates that there is an edge that connects node $$$i+1$$$ to node $$$p_i$$$ and all the edges also guarantee a tree (usually this comes with the $$$1 \leq p_i \leq i$$$ constraint to do that)? I personally prefer the latter.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

unrooted tree former, rooted tree latter. For rooted trees a lot of things (such as DP) get a much more easier implementation with the latter input. For unrooted trees I like to just treat them the same way as I do for usual undirected graphs

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unrooted (first)

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The first one. I think this is easier to use when trying to create a specific test case because we don't need to look at the input sequence to know what node does that node is connected to.

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Depends on the problem