"1 5" означава, че има връзка между двата node-а

иначе можеш и 1 да си го изкараш като корен, няма да има значение, пак е същия отговорът (важното е, че листата си остават същите) : )

за първия ред и аз не съм сигурна, но попринцип в задачи се дават ограничения за това N и така знаеш колко памет ти трябва, дали ще имаш time limit и т.н.

Не би трябвало да е така, трябва ясно да е дефинирано кое е родител и кое дете, а във всички останали случаи във входните данни подредбата е правилна. В противен случай може всеки нод да разглеждаш като корен и няма да има начин да търсиш листата, понеже всеки нод ще има деца и родител; няма как да търсиш нодове без деца с тази дефиниция, защото такива просто няма.

И според мен е грешен входа. Ако беше така корена трябва да е 1, а не 5. Факт е, че решението може да работи и с този вход и да дава правилен изход, но определено не е коректно. Единствено не разбрах какво се очаква да направим по 1-ва задача. Там противоречията са много и няма как човек да си изгради единна теория за това как би могло да е коректното условие. Надявах се да се доизясни, но изглежда, че ще си остане така.

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

При моето решение ще оставя програмата да връща отговор, че даденото е гора в последните два примера, дано оценяващите не се водят само по примерите.

Поправихме ребрато: 1 5 -> 5 1.

Ако връзките са двупосочни, задачата също може да се реши, но малко по-сложно.

Наков

Мисля, че има грешка и в насоките (hints) на 4-та задача. Ако разгледаме случая например когато най-дългият път по сума е от 1 листо до друго което му е sibling (имат общ родител) тогава решението с намирането на пътя до корена от всяко листо няма да работи. Никъде не пише че пътя трябва да минава задължително през корена. Ако съм разбрал правилно, то тогава решението се усложнява.

Аз доколкото разбирам задачата (4-та) трябва да се разгледат сумите между две листа до първия им общ родител. Ако задължително трябва да се мине през корена това означава или 1) едни и същи нодове да участват в сумата ако вземем две листа от една и съща страна на корена (което според примера не е така), 2) да се вземе едно листо принадлежащо на левия наследник на корена и едно на десния.

Аз направих задачата като взимах сумите до първия общ родител, тъй като това е директният път между двете листа.

nakov, има дори в примера отрицателна стойност на нод. Дори и да няма отрицателни стойности, пак може 2 нода със общ "баща" да са с най-голяма сума. Тогава трябва да се мине по 1 и същи път 2 пъти както е казал Filkolev, за да мине през корена, в което и аз не намирам голяма логика.

Filkolev, да, и аз мисля, че трябва да е до общ родител, защото това е пътя от 1 листо до друго. Ако това се иска реално от задачата, трябва да се поправят hint-овете, защото виждам повечето са го направили както е указано в тях. А е добре и още един пример да се добави, който не минава през корена ;).

Оправих hint-а на задачата "Problem 4. Longest Path in a Tree". Идеята е за всяка двойка върхове да се намери пътя между тях и от всички такива пътища да се избере най-голямата сума.

За да се оптимизира пресмятането на сумата за пътя между двойка върхове да става със сложност O(1) и съответно цялата задача да се реши със сложност O(N*N), се смята пътя от всеки връх до корена + малко сметки за да се сметне пътя между всяка двойка върхове.

Имаше грешка в hints: пишеше, че всеки път трябва да минава през корена, но не е така.

Наков

Благодаря :)

А какъв начин използвате за изчлисляване на "nearest common parent" ​и най-вече каква е сложността на алгоритъма (питам тези, които са решили задачата с път през най-близкия общ родител).