Дерево на n вершинах. На рёбрах дерева написаны целые числа в двоичной записи (можее считать, что все имеют одинаковое к

@Salamani · Регистрация: 06.05.2019

Студворк — интернет-сервис помощи студентам

Дерево на n вершинах. На рёбрах дерева написаны целые числа в двоичной записи (можее считать, что все имеют одинаковое количество двоичных разрядов).
Требуется уметь находить xor всех чисел на рёбрах пути из вершины u в вершину v для любых заданных пользователем вершин u в вершину v. Операция xor — это побитовое исключающее или. Например, 1010 xor 1100 = 0110.
(a) Во многих ситуациях бывает полезно сделать предподсчёт: заранее произвести некоторые вычисления и сохранить их результаты в памяти, чтобы в дальнейшем ускорить вычисления. Простой пример: если нам дан некоторый текст и нужно уметь быстро отвечать на запросы вида “сколько раз слово x встречается в тексте после слова y”, то можно заранее подсчитать, сколько раз встречается в тексте каждое словосочетание из двух слов, и это позволит в дальнейшем очень быстро отвечать на вопрос (за стоимость запроса к памяти). Приду- майте какой-либо вариант предподсчёта для задачи вычисления xor вдоль путей. Оцените, сколько операций потребует предпосчёт, сравните число операций, требуемое для вычисления xor вдоль пути без предподсчёта и с использованием предложенного вами способа предподсчёта.
(b) Придумайть, как выполнить некоторый предпосчёт за время O(n), который позволит впоследствии отве- чать на запрос xor за время O(1).

Помогите, пожалуйста, с данной задачей.

@salam · 28.07.2019, 16:22

подсказка: c xor d = (a xor b xor c xor d) xor (a xor b)

@dupeljan · 30.07.2020, 16:53

Пусть граф $https://www.cyberforum.ru/cgi-bin/latex.cgi?G = (U,V)$ . Выберем любую вершину $https://www.cyberforum.ru/cgi-bin/latex.cgi? r \in U$ и посчитаем для каждой вершины значение $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_r^k = \oplus(r,a_1,...,a_k)$ где $https://www.cyberforum.ru/cgi-bin/latex.cgi?(r,a_1,...,a_k)$ - путь из вершины в вершину $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_k$ . Это можно сделать поиском в глубину. Величины $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_r^k$ сохраним в словарь с ключем $https://www.cyberforum.ru/cgi-bin/latex.cgi?k$ .

Пусть путь из u до v проходит через корень. Тогда по ассоциативности и коммутативности операции xor
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A_u^v = A_1^u \oplus A_1^v$

Пусть путь из u до v не проходит через корень. Пусть самый верхний общий предок u и v - вершина k, $https://www.cyberforum.ru/cgi-bin/latex.cgi? k \neq r$ . Так как в дереве пути для всех пар вершин единственные, то $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_1^u = A_1^k \oplus A_k^u$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_1^v = A_1^k \oplus A_k^v$ . Из свойства $https://www.cyberforum.ru/cgi-bin/latex.cgi? a \oplus a = 0$ получаем

$https://www.cyberforum.ru/cgi-bin/latex.cgi?A_1^u \oplus A_1^v = A_k^u \oplus A_k^v$ -случай 1 для поддерева с корнем k.

Таким образом $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_u^v = A_1^u \oplus A_1^v \forall v,u \in V$ . Сложность предподсчета O(n), сложность поиска по словарю O(1).

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Salamani 3 / 3 / 0 Регистрация: 06.05.2019 Сообщений: 95

	Дерево на n вершинах. На рёбрах дерева написаны целые числа в двоичной записи (можее считать, что все имеют одинаковое к 26.07.2019, 13:45. Показов 2824. Ответов 2 Метки нет (Все метки) Дерево на n вершинах. На рёбрах дерева написаны целые числа в двоичной записи (можее считать, что все имеют одинаковое количество двоичных разрядов). Требуется уметь находить xor всех чисел на рёбрах пути из вершины u в вершину v для любых заданных пользователем вершин u в вершину v. Операция xor — это побитовое исключающее или. Например, 1010 xor 1100 = 0110. (a) Во многих ситуациях бывает полезно сделать предподсчёт: заранее произвести некоторые вычисления и сохранить их результаты в памяти, чтобы в дальнейшем ускорить вычисления. Простой пример: если нам дан некоторый текст и нужно уметь быстро отвечать на запросы вида “сколько раз слово x встречается в тексте после слова y”, то можно заранее подсчитать, сколько раз встречается в тексте каждое словосочетание из двух слов, и это позволит в дальнейшем очень быстро отвечать на вопрос (за стоимость запроса к памяти). Приду- майте какой-либо вариант предподсчёта для задачи вычисления xor вдоль путей. Оцените, сколько операций потребует предпосчёт, сравните число операций, требуемое для вычисления xor вдоль пути без предподсчёта и с использованием предложенного вами способа предподсчёта. (b) Придумайть, как выполнить некоторый предпосчёт за время O(n), который позволит впоследствии отве- чать на запрос xor за время O(1). Помогите, пожалуйста, с данной задачей. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	28.07.2019, 16:22
	подсказка: c xor d = (a xor b xor c xor d) xor (a xor b) 0

@dupeljan 1 / 1 / 0 Регистрация: 20.11.2018 Сообщений: 1
	30.07.2020, 16:53
	Пусть граф $https://www.cyberforum.ru/cgi-bin/latex.cgi?G = (U,V)$ . Выберем любую вершину $https://www.cyberforum.ru/cgi-bin/latex.cgi? r \in U$ и посчитаем для каждой вершины значение $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_r^k = \oplus(r,a_1,...,a_k)$ где $https://www.cyberforum.ru/cgi-bin/latex.cgi?(r,a_1,...,a_k)$ - путь из вершины в вершину $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_k$ . Это можно сделать поиском в глубину. Величины $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_r^k$ сохраним в словарь с ключем $https://www.cyberforum.ru/cgi-bin/latex.cgi?k$ . Пусть путь из u до v проходит через корень. Тогда по ассоциативности и коммутативности операции xor $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_u^v = A_1^u \oplus A_1^v$ Пусть путь из u до v не проходит через корень. Пусть самый верхний общий предок u и v - вершина k, $https://www.cyberforum.ru/cgi-bin/latex.cgi? k \neq r$ . Так как в дереве пути для всех пар вершин единственные, то $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_1^u = A_1^k \oplus A_k^u$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_1^v = A_1^k \oplus A_k^v$ . Из свойства $https://www.cyberforum.ru/cgi-bin/latex.cgi? a \oplus a = 0$ получаем $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_1^u \oplus A_1^v = A_k^u \oplus A_k^v$ -случай 1 для поддерева с корнем k. Таким образом $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_u^v = A_1^u \oplus A_1^v \forall v,u \in V$ . Сложность предподсчета O(n), сложность поиска по словарю O(1). 1