DP дар дарахт (Tree DP)
DP дар дарахт — ин синфи масъалаҳост, ки дар он қиматҳо дар қулла дар асоси қиматҳои фарзандони он дар дарахти DFS ҳисоб карда мешаванд.
Диаметри дарахт
Диаметр — дарозии роҳи соддаи максималӣ байни ду қуллаи дарахт.
Идеяи классикии DP:
Барои ҳар қуллаи ҳисоб мекунем:
- — чуқурии максималии роҳ ба поён (то ягон фарзанд)
Он гоҳ роҳе, ки аз мегузарад: