转载自：http://blog.csdn.net/wenlei_zhouwl/article/details/5992704
问题：Stewart教授是一家公司总裁的顾问，这家公司计划一个公司聚会。这个公司有一个层次结构；也就是，管理关系形成一棵以总裁为根的树。人事部给每个雇员以喜欢聚会的程度来排名，这是一个实数。为了使每个参加者都喜欢这个聚会，总裁不希望一个雇员和他（她）的直接上司同时参加。
Stewart教授面对一颗描述公司结构的树，使用了10.4节描述的左子女、右兄弟表示法。树中每个节点除了包含指针，还包含雇员的名字以及该雇员喜欢聚会的排名。描述一个算法，它生成一张客人列表，使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。
分析：
对每个节点添加两个域SelectRoot和UnselRoot。SelectRoot意味着当该节点被选择时，以该节点为根的子树的最大聚会喜欢程度。UnselRoot意味着当该节点不被选择时，以该节点为根的子树的最大聚会喜欢程度。
假设原先每个节点的两个域名字和聚会喜欢程度为Name,Like。初始时，每个叶子节点的SelectRoot为其Like值，UnselRoot为0。
依次向上计算每个节点的SelectRoot和UnselRoot值
最终只需要查看总裁节点，取其SelectRoot和UnselRoot中的最大值。
要记录客人列表，则只需从树的的第二层开始，每一层做如下操作：如果parent被选，则当前层都不选；如果parent未被选，则看当前层中每个节点的SelectRoot和UselRoot的大小关系，如果SelectRoot大，则选中该节点，否则，不选该节点。遍历完树之后，参加的客人便都标记出来了。
计算n个节点的SelectRoot和UnselRoot，每次计算都只使用子节点的域值，所以整个计算的过程也只累加了树中除了根的其它节点的域值（每个节点就被用一次）。所以算法复杂度为O(n)。