Stewart教授是一家公司总裁的顾问，这家公司计划一个公司聚会。这个公司有一个层次式的结构；也就是说，管理关系形成一棵以总裁为根的树。人事部给每个雇员以喜欢聚会的程度来排名，这是个实数。为了使每个参加者都喜欢这个聚会，总裁不希望一个雇员和他（她）的直接上司同时参加。
Stewart教授面对一棵描述公司结构的树，使用了左子女、右兄弟表示法。树中每个结点除了包含指针，还包含雇员的名字和该雇员喜欢聚会的排名。描述一个算法，它生成一张客人列表，使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。
分析：假设有一棵公司结构树，如下图所示：
A是根结点，代表总裁。A是B、C、D的直接上司，因此A与B，A与C，A与D都不可以同时出现在列表中。
定义：PartyLoveSum(N),表示以N为根结点的子树得到的最优客人列表的喜欢聚会程度的总和。
结点N只有两种情况，要么参加，要么不参加。所以
PartyLoveSum(N) = PartyLoveSum(N.go),或者 PartyLoveSum(N) = PartyLoveSum(N.nogo)。
因此，要生成整个公司结构树的最优客人列表，使得客人喜欢聚会的程度总和最大，就是求PartyLoveSum(A)。
假设知道A的每个孩子结点的PartyLoveSum，即已知PartyLoveSum(B.go),PartyLoveSum(B.nogo);PartyLoveSum(C.go),PartyLoveSum(C.nogo);PartyLoveSum(D.go),PartyLoveSum(D.nogo);
那么求出下面两种情况PartyLoveSum(A)的值，选择值最大的情况。
1. A去，PartyLoveSum(A) = PartyLoveSum(A.go)
A要参加，A的直接下属都不能参加 PartyLoveSum(A.go) = A.partylove + 
2. A不去，PartyLoveSum(A) = PartyLoveSum(A.nogo)
A若是不参加，A的直接下属可参在，也可不参加。
PartyLoveSum(A.nogo) = 
一旦知道A是否参加的情况，就能决定其孩子结点是否参加，孩子结点再决定它的孩子结点是否参加。
因此，算法需要两次遍历公司结构树，第一次是计算每个结点的PartyLoveSum，第二次决定每个结点是否参加。
算法如下：
ComputePartyLoveSum( Node N)
if N has no children
PartyLoveSum(N.nogo) = 0;
PartyLoveSum(N.go) = N.partylove;
return;
end if
for each child c in N.children
ComputePartyLoveSum(c);
end for
PartyLoveSum(N.go) = N.partylove +
PartyLoveSum(N.nogo) =
下面是判断结点是否参加的算法
DecideAttendOrNot(Node N)
parent = getParent(N);
if parent == null //N是根结点
PartyLoveSum(N.go) > PartyLoveSum(N.nogo) ? N.decide = go : N.decide = nogo
else
if parent.decide == go
N.decide = nogo;
else
PartyLoveSum(N.go) > PartyLoveSum(N.nogo) ? N.decide = go : N.decide = nogo;
end if
end if
if N has children
for each child c in N.children
DecideAttendOrNot(c);
end for
end if
两次遍历，算法的执行时间为 O(2n)，n为结点的个数。