주어진 (반드시 바이너리는 아님) 트리의 최대 합계 바이너리 서브 트리 찾기

Question

노드에 정수 (양수/음수) lables가있는 (바이너리가 아닐 수도 있음) 트리를 받았으며,이 트리를 최대화하는 바이너리 하위 트리를 찾아야합니다. 나무에있는 lables의 합계. 동적 프로그래밍 접근법에 대해 생각해 보았습니다. 저는 u에 뿌리를 둔 모든 이진 트리에 대해 최대 합계를 반환하는 f (u)를 정의하고 v, w를 선택하여 f (u)를 계산했습니다. u의 모든 자식 쌍에 대해 sum (f (v) + f (w))을 구한 다음 f (u) = label (u) + f (v) + f f는 전형적인 다이나믹 프로그래밍 접근법에서 리프 업 (leaf up)으로부터 계산 될 수있다. 내 질문 :

(1) 더 효율적인 접근 방법은 무엇입니까? (2) 가장 비용이 많이 드는 단계는 u의 모든 자녀 쌍 중 최대를 찾는 것입니다. u가 n 명의 자녀가있는 경우 비용은 O (n^2)이지만 전체 트리의 경우 O보다 작습니다 | E |^2), 사실입니까? 비용을 더 정확하게 계산하려면 어떻게해야합니까?

감사합니다.

Answer 1

노드 U에 n 자식이있는 경우 f (V)와 f (W)를 최대화하는 자식을 가져 와서 f (U)를 최대화하는 V, W 쌍을 찾을 수 있습니다. 실제로 각 쌍을 검사 할 필요는 없습니다. 당신은 쉽게 할 수있는 오히려 O (N²)를 필요로하는 것보다 O (2 N)   =   O (N).

예를 들어 자식 노드가 f 값이 {6, 5, 2, 12, 8}이면 8과 12 인 두 개의 가장 큰 값만 있으면됩니다. 실제로 각 노드를 검사 할 필요는 없습니다 값 쌍을 명시 적으로 추가하십시오.

(참고 :.? 중 선택된 노드가 음의 F 값이있는 경우, 당신은 그냥 드롭해야 이진 트리가 하나 자녀와 함께 내부 노드를 허용합니까)