Что-то вроде сканлайна по графу

Правка ru1, от NekoKarp, 2019-01-19 23:29:24

Есть такая задача: дано подвешенное дерево и запросы к нему. Каждый запрос — путь в графе, причём LCA концов границ этого отрезка — одна из этих границ. В каждой вершине написано число от 0 до n. Для каждого запроса в порядке их поступления требуется идя по нему от 1 границы до другой занулить все вершины, которые равны n, исключая края отрезков таких вершин. Иными словами, если на этом пути встречаются несколько подряд идущих вершин равных n, то с первой и последней из них мы ничего не делаем, а остальным присваиваем 0. Я предполагаю, что данную задачу можно решить сканлайном вида "будем обходить дерево DFS-ом и заходя в вершину, из которой начинается отрезок начинаем занулять, проверяя не конец ли текущая вершина", но по неизвестным причинам такой способ получает WA(вероятно из-за порядка запросов, а он, как видно из условия, важен), был бы рад, если бы кто-нибудь поможет с этой задачей. Желательно предоставить конкретную реализацию или доказательство, что моя идея ошибочна.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский NekoKarp 2019-01-19 23:29:24 1036 Первая редакция (опубликовано)