HexShift's blog

By HexShift, history, 15 months ago, In English

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.

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

| Write comment?
»
15 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

unrooted (first)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Depends on the problem