{"problem":{"name":"A. Рудольф и дрессировка","description":{"content":"У Рудольфа есть любимая собачка, которую зовут Байер. Как и всякий ответственный хозяин, Рудольф старается воспитывать своего питомца и учит его выполнять различные команды. Однако традиционные трюки ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10132A"},"statements":[{"statement_type":"Markdown","content":"У Рудольфа есть любимая собачка, которую зовут Байер. Как и всякий ответственный хозяин, Рудольф старается воспитывать своего питомца и учит его выполнять различные команды. Однако традиционные трюки вроде «_Сидеть_» и «_Апорт_» не очень-то и впечатляют Рудольфа, поэтому он придумал для Байера кое-что получше. Рудольф — большой фанат структур данных, в связи с чем он предлагает Байеру рисовать красно-чёрные деревья.\n\nКрасно-чёрное дерево — это древовидная структура данных, имеющая следующие особенности: \n\nСегодня Рудольф решил пообедать в своём любимом кафе. К сожалению, туда не пускают с животными, поэтому Байеру придётся остаться дома. Чтобы питомцу не было грустно, Рудольф поручил ему составить примеры красно-чёрных деревьев. Байер с радостью согласился и с энтузиазмом взялся за работу.\n\nЧерез три часа Рудольф вернулся из кафе сытый и довольный. К своему удивлению, он обнаружил, что Байер успел нарисовать огромное количество красно-чёрных деревьев: среди них были маленькие, средние, большие и даже очень большие. Рудольф смог визуально оценить только деревья небольшого размера и нашёл несколько ошибок. А вот проверить остальные деревья оказалось очень сложно, поэтому Рудольф попросил вас автоматизировать оценку трудов Байера.\n\nПервая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева. \n\nСледующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi =  - 1.\n\nГарантируется, что описанный во входных данных граф является деревом и имеет корень.\n\nВыведите «_YES_» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «_NO_» (без кавычек).\n\n## Входные Данные\n\nПервая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева. Следующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi =  - 1.Гарантируется, что описанный во входных данных граф является деревом и имеет корень.\n\n## Выходные Данные\n\nВыведите «_YES_» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «_NO_» (без кавычек).\n\n## Примеры\n\nВходные данные5red 30 40black 20 -1black 10 20black 40 20red 50 40Выходные данныеYESВходные данные5red 3 4red 5 4black 2 -1black 1 2red 4 2Выходные данныеNO\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of internal nodes.  \nLet $ V = \\{v_1, \\dots, v_n\\} $ be the set of internal nodes, where each node $ v_i $ is characterized by:  \n- $ c_i \\in \\{\\text{red}, \\text{black}\\} $: color of the node,  \n- $ k_i \\in \\mathbb{Z} $: key of the node,  \n- $ p_i \\in \\mathbb{Z} \\cup \\{-1\\} $: key of the parent node ($ p_i = -1 $ iff $ v_i $ is root).  \n\nLet $ T $ be the tree structure induced by parent-child relationships. Add external (leaf) nodes (black, key-less) as children where needed to satisfy red-black tree properties.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq k_i, p_i \\leq 10^{18} $ for all $ i $, and $ p_i = -1 $ for exactly one node (the root).  \n3. The graph is a tree with unique root.  \n4. All keys are distinct.\n\n**Objective**  \nDetermine whether $ T $, with added black leaf nodes, satisfies all red-black tree properties:  \n\n1. Every node is either red or black.  \n2. The root is black.  \n3. Every leaf (external node) is black.  \n4. If a node is red, then both its children are black.  \n5. For each node, all simple paths from it to descendant leaves contain the same number of black nodes (black-height).  \n\nOutput \"YES\" if all properties hold; otherwise, output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10132A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}