trees

Daraxt — sikli yo‘q bog‘langan graf: n ta uch va n − 1 ta qirra. Bitta uchni ildiz deb tanlasak, har uchning ota-onasi va bolalari bo‘ladi.

Saqlash va aylanish

g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1); g[v - 1].append(u - 1)

def dfs(v, parent):
    size = 1
    for to in g[v]:
        if to != parent:
            size += dfs(to, v)          # qism daraxt hajmi
    return size

Asosiy tushunchalar

• Chuqurlik — ildizdan masofa; balandlik — eng uzoq bargcha.
• Ikkilik qidiruv daraxti: chapda kichiklar, o‘ngda kattalar.
• Diametr: istalgan uchdan eng uzoq a ni toping, a dan eng uzoq b — a–b diametr (ikki marta BFS/DFS).

Daraxtda DP ko‘p uchraydi: har uch uchun javob bolalarining javobidan yig‘iladi.