FineLine's blog

Doubt in CODEFORCES 161D
By FineLine, history, 9 years ago, In English

__Hi everyone.I was trying to practice DP and then I encountered this question 161D - Distance in Tree.I have got the basic idea But I do not know how the editorialist gave the second recurrence relation. Can anyone please spare his precious time and help me regarding the same. Regards and Thanks in advance.

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

So v is a vertex and u is one of his sons.

First notice that if x is a node in subtree of u then -> dis(u,x) = dis(v,x)-1

Then notice that in array d[v] we included u's subtree too.

So the number of nodes that are in subtree of v but not in subtree of u and have distance k from v are d[v][k]-d[u][k-1].

According to these, when we are calculating the sigma , we must calc nodes with distance x-1 from subtree of u and k-x from subtree of v but exclude those are in the subtree of u (from second one).

→ Reply