мне нужен алгоритм, который может решить эту проблему ниже эффективно:времени эффективный алгоритм Tree
дано дерево (не двоичным) с максимумом 200000 ребер и 3 узлов х, у, г. Напишите алгоритм, который возвращает true, если либо y лежит в пути x и z, либо z лежит на пути x и y. Количество запросов составляет порядка 10^5.
Понятное дело. Так как это дерево, чтобы проверить на x -> y -> z, начните с z, затем перейдите к корню дерева. Аналогично, для проверки на x -> z -> y, начинайте с y, затем переходите к корню дерева. Вы могли бы, конечно, начинать с z и y в то же время и проходить по дереву к корню, пока не найдете, что выполнено одно из двух условий пути, или вы найдете противоречивую информацию, такую как «z» и «y», принадлежащих двум разным ветвям «x», или не находя x, даже когда вы прошли весь путь до корня.
В худшем случае для этого простого алгоритма будет иметь место, когда у вас есть полностью линейное дерево с причем каждый узел имеет только одного ребенка, так что x является корнем, y является 100000 края от x (т.е. половина пути), и z это лист. Я не знаю, откуда взялся предел 10^5.
Извините, но Stack Overflow - это не «моя домашняя работа для меня». Что вы пробовали? Как это случилось? – svick
@svick фактически эта проблема сужается до проблемы, т.е. нахождение минимального общего предка двух узлов в неориентированном графе или дереве (а не двоичном дереве). Нужна помощь в этом отношении. Извините, я отправил свою проблему в переполнение стека. Я сделал некоторые ограничения времени ... Может ли PL PLUS предложить мне какой-то алгоритм? – geek2geek
@svick: Вы можете просто VTC эти вещи. – tmyklebu