1018. Двоичная яблоня (ДП, структура данных) [acm.timus.ru]

[Условие]

Основная идея:
В ходе решения встают следующие вопросы:
1) Как хранить дерево?
2) Как его получить, используя входные данные?
3) Что дальше делать с этим деревом?
Начнем по порядку:

1)Как хранить дерево?
Хранить нужно ребра и связи между вершинами. Рассмотрим следующие структуры: 

1. #define MAX_SIZE 102
2. struct edge
3. {
4.   int num;
5.   int weight;
6.   edge()
7.   {
8.     num = 0;
9.     weight = 0;
10.   }
11.   edge(int n ,int w)
12.   {
13.     num = n;
14.     weight = w;
15.   }
16. };
17. struct vertex
18. {
19.   edge left,right;
20. };
21. vertex adj[MAX_SIZE]; // двоичное дерево

Все дерево храним в массиве adj. Каждый элемент дерева имеет два ребра left(левый сын) и right (правый сын). В свою очередь каждое ребро указывает на номер, на который ссылается ребро(num) и вес ребра(weight). Нумерация вершин идет с единицы, поэтому, если ребро ссылается на вершину 0, считаем, что ребра просто нет.

2)Как получить дерево?
Входные данные можно хранить в виде матрицы смежности int adjMatrix[MAX_SIZE][MAX_SIZE], где элемент  adjMatrix[i][j] показывает вес, между вершинами i и j. Если вес равен 0, значит вершины не связные. Каждая вершина имеет до 3 смежных вершин. При этом если смежная вершина всего одна, то это рассматриваемая вершина является листом. Также известно, что корневая вершина является 1. Использую все эти данные можно заполнить массив adj с помощью поиска в глубину:

1. int edgesAmount[MAX_SIZE]; // количество дочерних ребер
2.  
3. void dfs(int num)
4. {
5.   bool isLeft = true;
6.   for (int i=1;i<=n;i++)
7.   {
8.     if (adjMatrix[num][i])
9.     {
10.       if (isLeft)
11.         adj[num].left = edge(i,adjMatrix[num][i]);
12.       else
13.         adj[num].right = edge(i,adjMatrix[num][i]);
14.      
15.       isLeft = false;
16.       adjMatrix[num][i] = adjMatrix[i][num] = 0;
17.      
18.       dfs(i);
19.  
20.       edgesAmount[num] += edgesAmount[i] + 1;
21.     }
22.   }
23. }

По ходу заполнения массива adj исходная матрица смежности затирается нулями, чтобы каждое ребро считалось не более 1 раза.

3) Что делать с полученным деревом?
Итак мы подошли к самому интересному. Задача решается методом динамического программирования.
Заведем функцию f(num,edges) – значение которой равно максимальной сумме ребер, дочерних вершине num, количество которых равно edges. Как несложно догадаться f (1,totalEdges) и будет являться ответом на нашу задачу, где totalEdges – общее количество ребер в результирующем дереве.
Рассмотрим вершину num, для которой нужно определить значения функции f для edges = {0,1,2,3..} 
3.1) f(num,0) = 0
3.2) если edges = 1. Если текущая вершина не является листом, то ответом будет максимальный вес правого или левого ребра. Если же текущая вершина является листом см. пункт 3.3)
3.3) Если количество дочерних ребер меньше, чем количество ребер, которые должны быть задействованы для текущей вершины, то это невозможная ситуация и мы должны исключить рассматриваемый вариант из множество возможных решений. Это легко сделать, если функция f при этом будет возвращать маленькое отрицательное значение.
3.4) Если edges = 2, то уже возникает несколько случаев. Можно построить до 5 поддерьев с корнем в текущей вершине:

Для поддерева:

     4   5 6   7
      \ /   \ /
       2     3
        \   /
          1

Варианты:
1-2-4 (1)
1-2-5 (2)
1-3-6 (3)
1-3-7 (4)

  1   (5)
_/ \_
2   3
Каждый из этих случаев можно отдельно рассмотреть используя пункты 3.1 – 3.3 и найти итоговый ответ для текущей вершины.
Для ускорения работы программы заведем матрицу int mem[MAX_SIZE][MAX_SIZE] в которой будем хранить уже подсчитанные значения  функции f для пар (num, edges). Детали реализации см. исходник (функция f).

[Исходный код]