Ditchers
Национална Олимпиада по Информатика 2014, Контролно 3
Time Limit: 0.2s, Memory Limit: 64MiB
Ели и нейните съученици участват в два училищни проекта. Във всеки от проектите участват всички N ученици (включително Ели). За да не настане пълна анархия, учителките са направили йерархия за всеки от проектите – кой ученик отговаря за кои ученици, те пък за кои други и така нататък. Знае се, че йерархията на всеки от проектите е кореново дърво, но двете дървета не са задължително еднакви – например в едното някой от учениците може да е шеф на всички (корен на дървото), докато в другото той или тя да няма "подчинени" – тоест да е листо на дървото.

Учениците ги мързи, та две не виждат, затова са решили възможно най-много от тях да се скатаят (и да не вършат никаква работа). За да не видят две в бележника си, обаче, те трябва по такъв начин да подберат хората, които "изчезват", че все пак проектите да могат да бъдат завършени. За целта, за всеки от проектите, всеки ученик е казал минималния брой хора в неговото поддърво (екип) включително него самия, с които може да бъде завършена неговата част от проекта. Възможно е да се премахват както хора без подчинени (листа на дървото), така и такива, които имат подчинени. Единственото условие при премахването е във всяко поддърво от оригиналното дърво да останат поне толкова ученици, колкото е изискал коренът на поддървото (дори той да бъде един от премахнатите). Разгледайте примера за пояснение.

Сега учениците се питат колко най-много хора могат да бъдат премахнати (и от двата проекта), така че все пак проектите да могат да бъдат направени. Вие решавате да им помогнете, като напишете програма, която намира едно възможно такова множество от ученици.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – броят ученици. Следват N на брой реда, всеки съдържащ информацията за един ученик. Редът ще бъде форматиран като "Name: ManagerName1 Limit1 ManagerName2 Limit2", което означава, че ученикът е с име Name, "шефът" му (бащата на въпросния връх в дървото) в първия проект е ученикът с име ManagerName1, минималният брой хора в неговия подпроект в първия проект е Limit1, шефът му във втория проект е ученикът с име ManagerName2 и минималният брой хора в неговия подпроект във втория проект е Limit2. Ако даден ученик е корен на първото или второто дърво, то съответният ManagerName ще бъде "None". Гарантирано е, че никой от учениците няма да се казва по този начин.

Всички имена са последователност от малки и големи латински букви, без шпации или каквито и да било други символи. Всички имена са с дължина не по-голяма от 16 символа. Гарантирано е, че входът ще задава две валидни коренови дървета. Гарантирано е, че броят върхове в поддървото на всеки ученик (включително него самия) е по-голям или равен на минималния брой хора, които са нужни на този ученик в това дърво.
Изход
На първия ред на стандартния изход изведете едно цяло число R, указващо максималния брой ученици, които могат да бъдат премахнати от проектите. На следващия ред разделени с интервали изпечатайте R-те имена на учениците, които премахвате. Ако съществува повече от един възможен оптимален отговор, изпечатайте кой да е от тях.
Ограничения
  • 1 ≤ N ≤ 10,000
  • 0 ≤ Limit1i, Limit2iN
Примерен Вход Примерен Изход
8 Elly: None 4 Slavina 1 Kris: Elly 2 Stancho 0 Stancho: Elly 2 None 2 Slavina: Stancho 1 Stancho 3 Stoyan: Stancho 0 Kalina 0 Kiro: Kris 0 Stancho 1 Silvia: Stancho 0 Kiro 0 Kalina: Kris 0 Slavina 0 3 Stancho Kris Silvia
Проект 1: Ели е шеф на Крис и Станчо, Крис е шеф на Киро и Калина, докато Станчо е шеф на Силвия, Славина и Стоян. Ели е корен на дървото, Станчо и Крис са нейни преки подчинени и са на второто ниво на дървото, докато Киро, Калина, Силвия, Славина и Стоян са на третото ниво (и са листа на дървото). Ели е казала, че не може с по-малко от 4 човека, Крис е казала, че не може с по-малко от 2, Станчо е казал, че не може с по-малко от 2, Киро с 0, Калина с 0, Силвия с 0, Славина с 1 и Стоян с 0.
Едно от възможните дървета, които горните ограничения позволяват е като премахнем Ели, Калина, Силвия, и Стоян. В поддървото на Ели са останали точно четири човека (Станчо, Славина, Крис, и Киро); в поддърветата на Крис и Станчо са останали по двама души (което е и ограничението); в поддървото на Славина е останал 1 човек (отново ограничението); в поддървото на Киро е останал 1 човек (което е повече от долната граница 0).

Проект 2: Станчо е шеф на Крис, Киро, и Славина; Киро е шеф на Силвия; Славина е шеф на Ели и Калина; Калина е шеф на Стоян. Забележете, че това дърво е различно от дървото на първия проект.
За този проект Станчо е казал че ще му трябват поне 2 човека, Киро - поне 1; Славина – поне 3; Крис – поне 0; Силвия – поне 0; Ели – поне 1; Калина – поне 0; Стоян – поне 0.
Едно от решенията за този проект би било да оставим Киро, Славина, Ели и Калина (премахвайки останалите).

За цялата задача, обаче, показаните примерни премахвания са несъвместими, тъй като (ако например разгледаме премахнатите хора от втория проект) без Станчо, Силвия и Стоян в първия проект поддървото на Станчо остава с един единствен човек, при положение, че Станчо е казал, че ще са нужни поне двама.

Възможно решение за цялата задача (тоест и за двата проекта) би било да премахнем Станчо, Силвия и Крис.
Мрън!