Список заданий по продвинутым алгоритмам 2021 осень

1. $1 | p_i=1 | L_{max}$.
2. $1 | r_i, d_i=d | L_{max}$.
3. $1 | prec, r_i, p_i=1 | L_{max}$.
4. Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
5. $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
6. $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
7. $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
8. $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
9. $1 || \sum U_i$
10. $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
11. Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
12. Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
13. $P | pmtn, r_i | C_{max}$
14. $P | pmtn, r_i | L_{max}$
15. $Q | pmtn, r_i | C_{max}$
16. $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log n)$ (бонус за $O(n^3 \log\log n)$)
17. $P | p_i = 1 | \sum w_iU_i$ - доведите доказательство с пары до конца
18. $P | p_i = 1 | \sum w_iC_i$
19. $P | p_i = 1, pmtn | \sum w_iC_i$
20. $Q | pmtn | \sum C_i$
21. $Q | pmtn | \sum f_i$ (напомним, что f_i - произвольная неубывающая функция, может быть своя у каждой работы)
22. $Q | pmtn | f_{max}$
23. $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
24. Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
25. $P|intree, p_i=1|L_{max}$
26. $F | p_{ij} = 1 | \sum C_i$
27. $F2 | pmtn | C_{max}$
28. $F | p_{ij} = 1 | \sum U_i$
29. $F | p_{ij} = 1 | \sum w_iU_i$
30. $O | p_{ij} = 1 | C_{max}$
31. $O | p_{ij} = 1 | \sum C_i$
32. $O | p_{ij} = 1 | \sum w_iC_i$
33. $O | p_{ij} = 1, d_i | -$
34. $O | p_{ij} = 1 | \sum U_i$
35. $O | p_{ij} = 1 | \sum w_iU_i$
36. $O | p_{ij} = 1, r_i | C_{max}$
37. $O2 | p_{ij} = 1, prec | \sum C_i$
38. Обозначим как $BP(n)$ время умножения булевых матриц размера $n \times n$ над $\vee, \wedge$. Обозначим как $MM(n)$ время умножения целочисленных матриц размера $n \times n$ над $+, \times$. Докажите, что $BP(n) = O(MM(n))$.
39. Докажите, что можно найти транзитивное замыкание графа за время $O(BP(n))$.
40. Пусть $A$ и $B$ - матрицы размера $n \times n$. Пусть $R \subset \{1, 2, \ldots, n\}$, $|R|=r$. Обозначим как $A^R$ матрицу, которая получается из $A$ удалением всех столбцов, кроме столбцов из множества $R$. Аналогично, обозначим как $B_R$ матрицу, которая получается из $B$ удалением всех строк, кроме строк из множества $R$. Докажите, что произведение матриц $A^R\cdot B_R$ может быть найдено за время $O((n/r)^2 MM(r))$, где $MM(r)$ - время умножения матриц размером $r\times r$.
41. Пусть $MM(n)=2+\varepsilon$, $\varepsilon>0$. Модифицируйте алгоритм построения BPWM, чтобы он работал за $MM(n) \log n$. Почему эта идея не сработает, если $MM(n) = O(n^2)$?
42. Докажите лемму с лекции про то, что если в урне $n$ шаров, из которых $w$ белых и $n/2\le wr \le n$, а событие $A$ означает, что из $r$ наугад выбранных из урны шаров оказался ровно один белый, то $P(A) \ge 1/2e$.
43. Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
44. Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$.
45. Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
46. Вероятностный алгоритм поиска минимума некоторый функции от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
47. Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Можно ли найти верный ответ с вероятностью $99/100$ за полином от $n$?
48. Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $2/3$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
49. В алгоритме Кинг с лекции обозначим как $f(u)$ лист, которая получается в ветвящемся дереве $T'$ из вершины $u$ в исходном дереве $T$. Докажите, что если вес максимального ребра на пути из $u$ в $v$ в $T$ равен $x$, а вес максимального ребра на пути из $f(u)$ в $f(v)$ в $T'$ равен $x'$, то $x \ge x'$.
50. В условиях предыдущей задачи докажите, что то $x \le x'$.
51. Рассмотрим ветвящееся дерево, пусть в нем $n$ вершин. Пусть есть $m$ запросов на пары листьев, для которых необходимо найти максимальное ребро на пути. Разобьем каждый запрос на два запроса на вертикальном пути до $LCA$ этих листьев, таким образом имеем $2m$ вертикальных путей. Для вершины $v$ обозначим как $A(v)$ множество вертикальных путей, проходящих через $v$. Обозначим как $D_i$ множество вершин на расстоянии $i$ от корня, как $d_i$ число вершин на расстоянии $i$ от корня ($d_i=|D_i|$). Докажите, что $\sum\limits_{u\in D_i}\lceil\log(1+|A(u)|)\rceil<\sum\limits_{u\in D_i}\left(1+\log(1+|A(u)|)\right)\le d_i+d_i \log\frac{d_i+2m}{d_i}$.
52. В условиях предыдущей задачи докажите, что $\sum\limits_{i\ge 0}\left(d_i + d_i\log\frac{d_i+2m}{d_i}\right)\le n+n\log\frac{n+2m}{n}+2n$.
53. Докажите, что $\sum\limits_{u}\lceil\log(1+|A(u)|)\rceil = O(n + m)$.
54. Обозначим как $A[v]$ число, в котором $i$-й бит равен $1$, если в $A(v)$ есть путь, заканчивающийся на расстоянии $i$ от корня. Считайте, что вы можете решить задачу о $m$ запросах $LCA$ в дереве с $n$ вершинами за $O(n+m)$ (например, используя алгоритм Фарах-Колтона и Бендера, см https://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf). Объясните, как посчитать $A[v]$ за время $O(n+m)$.
55. Назовем вершину $v$ большой, если $|A(v)| > \log n/\log\log n$ и маленькой в противном случае. Докажите, что число больших вершин асимптотически не превышает $m /\log\log n$. Указание: оцените число больших вершин на каждом уровне дерева. Отдельно рассмотрите большие вершины на нижних $\log\log n$ и на остальных уровнях.
56. Для вершины $v$, для которой $|A(v)| = k$ рассмотрим фрагменты путей, лежащие выше вершины $v$. Будем хранить $B(v) = [l_1, l_2, \ldots, l_k]$ - список глубин самых тяжелых ребер на фрагментах путях, проходящих через $v$, в порядке от самого длинного пути к самому короткому. Иначе говоря, пронумеруем пути из $A(v)$ в порядке возрастания глубины их верхней вершины. Тогда $l_i$ - расстояние от корня до ребра, которое является самым тяжелым на пути от $v$ до некоторой вершины $u_i$, которая является верхним концом $i$-го пути. Числа $l_i$ называются тагами, длина тага $O(\log\log n)$. Докажите, что массив $B(v)$ отсортирован по неубыванию.
57. Пусть $p$ - родитель вершины $v$, как связаны массивы $B(p)$ и $B(v)$? Дайте подробное описание, используя, при необходимости, $A(p)$ и $A(v)$.
58. Для больших вершин $B(v)$ помещается в $O(\log\log n)$ машинных слово. Пусть родитель вершины также большой. Предложите алгоритм пересчета $B(v)$ через $B(p)$, $A[p]$ и $A[v]$ за $O(\log\log n)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$.
59. Обозначим как $bigp[v]$ максимальную глубину, на котором находится большой предок вершины $v$. Предложите алгоритм, как за построить массив $bigp$ по массиву $A$ за $O(n)$.
60. Для маленьких вершин $B(v)$ помещается в машинное слово, однако вместо списка $B(v)$ будем хранить вспомогательный список $C(v)$, устроенный так. Если самое тяжелое ребро на $i$-м по глубине пути из $A(v)$ находится ниже, чем $bigp[v]$, то будем хранить просто $l_i$. Иначе будем хранить $z_i$ - номер $l_i$ в $B(bigp[v])$. Обозначим упакованный в машинное слово список $C(v)$ за $C[v]$. Предложите алгоритм пересчета $С[v]$ за $O(1)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$. Вы можете использовать посчитанные для родителей и предков $C[u]$, $B(u)$, $A[u]$, $bigp[u]$.
61. Объедините результаты всех предыдущих заданий, чтобы получить алгоритм обработки $m$ запросов поиска максимального ребра на пути между двумя вершинами на дереве за $O(n+m)$.
62. Покажите, как свести задачу поиска минимального разреза в графе к $O(n)$ запускам алгоритма поиска минимального $s-t$ разреза.
63. Покажите, как свести задачу поиска минимального $s-t$ разреза в графе к полиномимальному числу запусков алгоритма поиска глобального минимального разреза.
64. Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
65. Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
66. Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
67. С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
68. Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
69. Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
70. Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
71. Докажите, что для полинома $p(x_1, \ldots, x_n)$ от $n$ переменных степени $d$ над полем $F$ и множества $S\subset F$ размера $s$ вероятность $P(p(x_1, \ldots, x_n)=0)\le d/s$, где вероятностное пространство - равновероятно все вектора $(x_1, \ldots, x_n)\in S^n$. Используйте без доказательства, что полином от одной переменной степени $d$ над любым полем имеет не более $d$ корней.
72. Покажите, что требование, что $F$ поле в предыдущей задаче является существенным, приведите пример полинома степени $d$ над кольцом, которое не является полем, имеющего более $d$ корней.
73. Покажите, что в определении PRAS можно заменить константу $3/4$ в требовании, что вероятность попасть в интервал $[1-\varepsilon;1+\varepsilon]$ должна быть $3/4$, на любое другое число, строго большее $1/2$.
74. Можно ли в предыдущем задании заменить $1/2$ на $0$?
75. Можно ли в решении задания 73 брать среднее значение в качестве оценки?
76. Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$,$ удовлетворяющее этот терм назначение переменных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы.
77. На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ.
78. Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении.
79. Почему алгоритм из предыдущего задания не работает для 3SAT?
80. Докажите, что оценку из задания 78 нельзя улучшить: предложите формулу, для которой в среднем понадобится $\Omega(n^2)$ случайных шагов для поиска удовлетворяющего назначения.
81. Предложите аналогичный заданию 78 алгоритм поиска раскраски графа в два цвета.
82. Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета?
83. Обозначим как $m_k(G)$ количество паросочетаний размера $k$ в двудольном графе $G$, каждая доля которого содержит по $n$ вершин. Пусть граф содержит больше $k$ ребер. Докажите, что существует ребро $uv$, такое что $m_k(G)/m_k(G\setminus uv) \le n$.
84. Пусть вероятностный алгоритм $U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем все паросочетания равновероятны. Покажите, как с использованием $U_k$ получить $\varepsilon$-$\delta$-FRPAS для доли паросочетаний, содержащих заданное ребро $uv$ в графе $G$.
85. Покажите, как с использованием $U_k$ из предедыдущего задания получить $\varepsilon$-$\delta$-FRPAS для числа $m_k(G)$.
86. Будем называть полиномиальный вероятностный алгоритм $U_k$ равномерным с точностью до $\rho$ генератором, если он получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем для любого паросочетания $M$ $|P(U_k(G)=M) - 1/m_k(G)| \le \rho/m_k(G)$. Пусть $\rho \le 1/n^b$ для некоторого $b$. Подберите константу $b$, чтобы можно было решить задание 84, используя равномерный с точностью до $\rho$ генератор.
87. Подберите константу $b$, чтобы можно было решить задание 85, используя равномерный с точностью до $\rho$ генератор.
88. Пусть полиномиальный вероятностный алгоритм $\hat U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$ или $k-1$, причем все паросочетания равновероятны. Пусть $r = m_k(G)/m_{k-1}(G)$ удовлетворяет условию $1/n^2 \le r \le n^2$. Докажите, что с помощью $\hat U_k$ можно получить $\varepsilon$-$\delta$-FRPAS для $m_k(G)$.
89. Подберите константу $b$, чтобы можно было решить задание 88, используя равномерный с точностью до $\rho \le 1/n^b$ генератор.
90. Докажите, что если степень любой вершины в графе не меньше $n/2$, то выполнено условие $1/n^2 \le r \le n^2$ для задания 88.
91. Соедините предыдущие задания, чтобы получить из существования равномерного с точностью до $\rho \le 1/n^b$ генератора $\hat U_k$ для любого $k$ $\varepsilon$-$\delta$-FPRAS для числа совершенных паросочетаний в двудольном графе, где степени всех вершин не меньше $n/2$.
92. Рассмотрим $\varepsilon$-$\delta$-FPRAS $A$ для числа паросочетаний в двудольном графе. Используя $A$, постройте полиномиальный вероятностный алгоритм, который является равномерным генератором с точностью до $\rho = o(1)$.
93. Пусть существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в двудольном графе, степень каждой вершины которого равна хотя бы $\beta n$, где $0 < \beta < 1$. Докажите, что существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в произвольном двудольном графе.
94. Рассмотрим алгоритм приближения числа $\pi$. Будем генерировать точки с равномерным распределением в квадрате $1 \times 1$ и считать долю попавших в круг диаметром 1, вписанный в этот квадрат. Оцените число итераций, необходимое, чтобы приблизить $\pi$ с точностью до $\varepsilon$.
95. Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 1). Докажите, что стационарное распределение $(1/n, 1/n, \ldots, 1/n)$.
96. Пусть матрицы $A$ и $B$ имеют один и тот же собственный вектор $x$ для собственных чисел $\lambda$ и $\mu$, соответственно. Докажите, что $x$ является собственным вектором для $A+B$. Для какого собственного числа?
97. Задача приблизительного подсчета числа вхождений. Biased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$++, а в качестве $query(x)$ будем возвращать $cnt[h(x)]$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Оцените $P(query(x) > a(x) + \varepsilon n)$.
98. CountMin. В предыдущей задаче чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $\min(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(query(x) > a(x) + \varepsilon n) < \delta$?
99. Задача приблизительного подсчета числа вхождений. Unbiased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства, а также случайную знаковую функцию $s: U \to \{-1,1\}$. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$ += s(x), а в качестве $query(x)$ будем возвращать $cnt[h(x)]\cdot s(x)$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Докажите, что $D[query(x)] \le \frac{1}{m}\sum_y a(y)^2$.
100. В условиях предыдущей задачи обозначим как $\lVert a \rVert_2 = \sqrt{\sum_x a(x)^2}$. Оцените $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2)$.
101. CountSketch В предыдущей задаче чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $median(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2) < \delta$?
102. Сравните оценки по времени, памяти и точности для CountMin и CountSketch. Сделайте вывод, когда какой из них лучше.
103. Поиск $k$ самых частых. Используем тот или иной аппроксимационный алгоритм (CountMin или CountSketch), мы хотим найти $k$ самых частых элементов в последовательности $a_1, \ldots, a_n$. Будем поддерживать $set$ из $k$ самых частых, упорядоченный по оценке на число их вхождений. Рассматривая очередной элемент, добавляем его в set, если его оценка на число вхождений становится больше, чем у самого редкого в $set$-е. Оцените вероятность, что для всех $x$ в $set$-е в конце выполнено $a(x) \ge (1-\varepsilon)a(y)$, где $y$ - это $k$-й по частоте встречаемости элемент.
104. Доминирующий элемент. Рассмотрим алгоритм, который ищет элемент, который встречается хотя бы $n/2$ раз в потоке $[a_1, \ldots, a_n]$. Пусть $0 \le a_i < N$ и $N \ge 2n$. Докажите, что детерминированный алгоритм, использующий $o(n\log(N/n))$ бит, не может решить поставленную задачу. Указание: рассмотрите состояние после половины элементов потока.
105. Предложите алгоритм, использующий $O(\log(N+n))$ бит, который решает предыдущую задачу в предположении, что доминирующий элемент существует.
106. Обобщите предыдущий алгоритм на случай $\varepsilon$-частых элементов: будем называть элемент $\varepsilon$-частым, если он составляет хотя бы $\varepsilon$ долю элементов во вводе. Как зависит память от $\varepsilon$?
107. Все различные. Докажите или опровергните, что любой детерминированный алгоритм, который всегда корректно отвечает, верно ли, что все элементы во вводе $[a_1, a_2, \ldots, a_n]$ различны, должен использовать хотя бы $\Omega(n\log(2N/n))$ памяти.
108. Недостающий элемент. Задан массив $[a_1, a_2, \ldots, a_{n-1}$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно один раз. Найдите недостающий элемент, используя $O(\log n)$ памяти.
109. Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{n-2}$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно один раз. Найдите недостающие элементы, используя $o(n)$ памяти.
110. Задана правильная скобочная последовательность с $n$ открывающими скобками. Рассмотрим четыре операции: findclose($i$) - найти закрывающую парную скобку для открывающей скобки на позиции $i$, findopen($i$) - найти открывающую парную скобку для закрывающей на позиции $i$, enclose($i$) - найти позицию открывающей скобки для пары скобок, непосредственно внутри которой находится открывающая скобка на позиции $i$, balance($i$) - найти баланс на позиции $i$. Используйте с rank и select с лекции, чтобы вычислить balance за $O(1)$ и $o(n)$ дополнительной памяти.
111. Используйте balance и идеи с лекции, чтобы реализовать $findclose$, $findopen$ и $enclose$.
112. Задано дерево (не обязательно двоичное) с порядком на детях. Для представления дерева используется правильная скобочная последовательность: запись вершины $u$ с детьми $v_1, v_2, \ldots, v_k$, обозначенная как $R(u)$ устроена так: $R(u) = (R(v_1)R(v_2)\ldots R(v_l))$. Опишите с помощью операций из задачи 110 операции: перехода к родителю, перехода к первому ребенку, перехода к следующему ребенку.
113. Размер поддерева. Опишите с помощью операций из задачи 110 способ узнать размер поддерева для заданной вершины.
114. Глубина вершины. Опишите с помощью операций из задач 110 способ узнать глубину вершины.
115. Опишите в терминах скобочных последовательностей операцию LCA. Предложите решение за $O(1)$ и $o(n)$ дополнительной памяти.