[算法]找树的重心

以前算法课作业做过这道题。今天在网上又碰到了。

给一个有n个结点的树，每个节点i都有一个正权重w(i),每条边j也有一个正权重c(j). 要求给出一个线性复杂度的算法，找出一个结点u，使得对其他所有结点i，w(i)*L(i)的总和最小，其中，L(i)为i到u路径上的所有边的权重和.

SOL: 本题贪心就足够了。记sumW为树上所有节点权重和(仅仅节点)以及WC_i[p]为以p为根的第i颗子树中所有节点权值和(仅仅节点)。如果P是重心，则　"sumW>2*WC_i[p]" 对于所有P的子树i成立--所有子树的权重都小于所有节点权重和的一半。为了找到满足这个条件的节点 用贪心就足够了。随便从一个节点开始，看到哪个子树的权重和超过所有节点权重和一半，就往那个子树移动。直到不能移动位置为止。