Изменения

==Динамика Главной особенностью [[динамическое программирование|динамического программирования]] по [[Дерево, эквивалентные определения | поддеревьям==]] является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.

{{Определение Задача| definition =Множество рёбер графаПусть задано взвешенное дерево, с весами, обозначенными как <tex>w_{i, такоеj}</tex>, что у любых двух рёбер нет общей где <tex>i</tex> и <tex>j</tex> — вершиныдерева, называется соединённые ребром.. Необходимо составить такое [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях | паросочетаниемпаросочетание]], чтобы суммарный вес всех рёбер, входящих в него, был максимальным.

Обозначим <tex>a[i]</tex> как паросочетание максимального веса в поддереве с корнем в <tex>i</tex>-той вершине, при этом <tex>i</tex>-тая вершина соединена ребром, входящим в паросочетание, с вершиной, входящей в поддерево <tex>i</tex>-ой вершины; аналогично <tex>b[i]</tex> {{-- -}} как паросочетание максимального веса в поддерева с корнем в <tex>i</tex>-той вершине, но только при этом <tex>i</tex>-тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево <tex>i</tex>-ой вершины; а <tex>c[i]=\max \left ( a[i],b[i] \right )</tex>, таким образом, ответ на задачу будет находиться в <tex>c[root]</tex>, где <tex>root</tex> {{--- }} корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине <tex>i</tex>, нам необходимо найти максимальное паросочетание для всех поддеревьев <tex>i</tex>-ой вершины.

Обозначим <tex>Ch(x) — </tex> {{---}} как множество сыновей вершины <tex>x </tex> и будем находить значения ''<tex>a'' [x]</tex> и ''<tex>b'' [x]</tex> следующим образом:

Если вершина <tex>x — </tex> {{---}} лист, то <tex>a[x]=b[x]=0</tex>,

Теперь оценим количество операций, необходимых нам для нахождения <tex>c[root]</tex>. Так как <tex>c[i]=\max \left ( a[i],b[i] \right )</tex>, то для вычисления <tex>c[root]</tex> необходимо вычислить <tex>a[root]</tex>, <tex>b[root]</tex>. Для вычисления и того, и другого необходимо время порядка <tex>O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )</tex>, где <tex> n </tex> — количество число вершин в дереве. 

===РеализацияПсевдокод === <font color =darkgreen>// в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] </font color =darkgreen> '''function''' dfs(x: '''int''', a: '''int[]''', b: '''int[]''', c: '''int[]''', w: '''int[][]''', Ch: '''int[]'''): '''for''' (i : Ch[x]) dfs(i, a, b, c, w, Ch) a[x] =max(a[x], b[i] + w[x][i] - с[i]) <font color = Псевдокод darkgreen>// по формуле выше, но без b[x] (прибавим его один раз в конце) </font color = darkgreen> b[x] += с[i] a[x] += b[x] <font color = darkgreen>// так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x</font color =darkgreen> c[x] =max(a[x], b[x])

dfs== Задача о сумме длин всех путей в дереве =={{Задача|definition = Найти сумму длин всех путей в дереве.}}Решим эту задачу за <tex> O(int n) </tex>. Пусть задано подвешенное дерево. Рассмотрим пути проходящие в поддереве вершины <tex> v </tex>. Во-первых, это пути, не проходящие через эту вершину, то есть все пути в поддеревьях её сыновей. Во-вторых, пути, которые оканчиваются вершиной <tex> v </tex>. И в-третьих, это пути, проходящие через вершину <tex> v </tex>, они начинаются из поддерева одного из сыновей этой вершины и заканчиваются в другом поддереве одного из сыновей вершины <tex> v </tex>. Теперь подсчитаем пути для каждого варианта. Обозначим <tex> S[v]\ - </tex> размер поддерева <tex> v </tex>, <tex> F[v]\ - </tex> сумма длин всех путей в поддереве вершины <tex> v </tex>, <tex> G[v]\ - </tex> сумма длин всех путей начинающихся в поддереве вершины v и оканчивающихся вершиной <tex> v </tex>, <tex> H[v]\ - </tex> сумма длин всех путей проходящих через вершину <tex> v </tex>. Если вершина <tex> u </tex> лист, то <tex> S[u] </tex> = 1, а <tex> G[u] </tex> = <tex> H[u] </tex> = 0.# Пути не проходящие через эту вершину. Это просто сумма суммы длин путей для всех поддеревьев детей или <tex> \sum_{x\in Ch(v):} \limits F[x]</tex>. for child # Пути оканчивающиеся в вершине <tex> v </tex>. Рассмотрим ребро, соединяющее вершину <tex> v </tex> и одного ее сына, пусть это будет вершина <tex> g </tex>. Переберем все пути, которые начинаются с этого ребра и идут вниз. Сумма длин всех таких путей будет сумма путей оканчивающихся в <tex> g + S[g] </tex>, так как суммарная длина путей оканчивающихся в вершине <tex> g </tex> уже сосчитана и каждый такой путь, которых ровно <tex> S[g] </tex> мы продлили ребром, соединяющим вершины <tex> v </tex> и <tex> g </tex>. Суммарная длина таких путей: <tex> G[v] = \sum_{x \in Ch(v)} \limits {\Bigl(G[x]+ S[x]\Bigl)}</tex>. dfs# Пути проходящие через вершину <tex> v </tex>. Рассмотрим двух сыновей этой вершины: <tex> x </tex> и <tex> y </tex>. Нам надо подсчитать все пути, которые поднимаются из поддерева <tex> x </tex> в <tex> v </tex> и затем опускаются в поддерево <tex> y </tex> и наоборот. То есть по каждому пути, оканчивающимся в вершине <tex> x </tex> мы пройдем столько раз сколько элементов в поддереве <tex> y </tex>, следовательно суммарная длина таких путей будет <tex> G[x]S[y] </tex>. Аналогично, если будем подниматься из поддерева <tex> y </tex>. Также надо учитывать сколько раз мы проходим по ребрам, соединяющим вершины <tex> x </tex> <tex> v </tex> и <tex> y </tex> <tex> x </tex>. Итого для двух вершин <tex> x </tex> и <tex> y </tex>: <tex> G[x]S[y] + G[y]S[x] + 2S[x]S[y] </tex>, следовательно ( <tex> x,y \in Ch(childv)</tex>); a<tex> H[xv] = max\sum_{x,y\ x \ne y} \limits{\Bigl(aG[x], bS[childy] + wG[y]S[x]+ 2S[childx] - сS[childy]\Bigl)} </tex>. Но такой подсчет испортит асимптотику до <tex> O(n^2); b</tex>. Заметим, что <tex> \sum_{x,y} \limits {\Bigl(G[x] +S[y]\Bigl)} = с\sum_{x} \limits {G[x]} \sum_{y} \limits {S[childy]; a} </tex>. Но еще надо учесть, что <tex> x \ne y </tex>, следовательно <tex> \sum_{x,y\ x \ne y} \limits{\Bigl(G[x] +S[y]\Bigl)} = b\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(G[x]S[x] c\Bigl)} </tex>. Аналогично для <tex> S[x]S[y] </tex>. Итак: <tex> H[v] = max\biggl(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(aG[x]S[x], b\Bigl)} \biggl) + \biggl(\sum_{x} \limits {S[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(S[x]S[x]\Bigl); } \biggl) </tex>. dfsОтвет задачи: <tex> F[v] = \sum_{x \in Ch(rootv); return c} \limits F[x] + G[v] + H[rootv];</tex>. Асимптотика каждого слагаемого равна <tex>O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )</tex>, где <tex> n </tex> — число вершин в дереве, следовательно и время работы самого алгоритма <tex> O \left (n \right ) </tex>.

==СсылкиСм. также==* [[Задача коммивояжера, ДП по подмножествам]]* [[Задача о числе путей в ациклическом графе]] ==Источники информации==*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895fc14aca73a4926918a879905ffcd4ad7a/timb86.pdf В. В. Лепин, Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве]* [http://ru.wikipedia.org/wiki/Паросочетание Википедия — Паросочетание]