Условие

В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.

Для каждого элемента дерева определите число всех его потомков (не считая его самого).

Примеры

Ввод: 9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I Вывод:

Alexander_I 0 Alexei 1 Anna 4 Elizabeth 0 Nicholaus_I 0 Paul_I 2 Peter_I 8 Peter_II 0 Peter_III 3

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine().toInt()
    val tree = mutableMapOf<String, MutableList<String>>() // Дерево родственных связей
    val descendants = mutableMapOf<String, Int>() // Число потомков
    val hasParent = mutableSetOf<String>() // Запоминаем всех, у кого есть родитель

    repeat(n - 1) {
        val (child, parent) = reader.readLine().split(" ")
        tree.computeIfAbsent(parent) { mutableListOf() }.add(child)
        hasParent.add(child)
        descendants[child] = 0
        descendants[parent] = 0
    }

    // Находим родоначальника (того, у кого нет родителя)
    val root = descendants.keys.find { it !in hasParent } ?: return

    // Функция для подсчёта потомков рекурсивно
    fun countDescendants(node: String): Int {
        val children = tree[node] ?: return 0
        var count = 0
        for (child in children) {
            count += 1 + countDescendants(child)
        }
        descendants[node] = count
        return count
    }

    countDescendants(root)

    // Вывод в лексикографическом порядке
    for (name in descendants.keys.sorted()) {
        writer.write("$name ${descendants[name]}\\n")
    }

    reader.close()
    writer.flush()
    writer.close()
}