weighted path length

Given an extended binary tree $T$ (that is, simply any complete binary tree, where leafs are denoted as external nodes), associate weights with each external node. The weighted path length of $T$ is the sum of the product of the weight and path length of each external node, over all external nodes.

Another formulation is that weighted path length is $\\sum w_{j}l_{j}$ over all external nodes $j$ , where $w_{j}$ is the weight of an external node $j$ , and $l_{j}$ is the distance from the root of the tree to $j$ . If $w_{j}=1$ for all $j$ , then weighted path length is exactly the same as external path length.

Example

Let $T$ be the following extended binary tree. Square nodes are external nodes, and circular nodes are internal nodes. Values in external nodes indicate weights, which are given in this problem, while values in internal nodes represent the weighted path length of subtrees rooted at those nodes, and are calculated from the given weights and the given tree. The weight of the tree as a whole is given at the root of the tree.

This tree happens to give the minimum weighted path length for this particular set of weights.

单词	WeightedPathLength
释义	weighted path length Given an extended binary tree $T$ (that is, simply any complete binary tree, where leafs are denoted as external nodes), associate weights with each external node. The weighted path length of $T$ is the sum of the product of the weight and path length of each external node, over all external nodes. Another formulation is that weighted path length is $\\sum w_{j}l_{j}$ over all external nodes $j$ , where $w_{j}$ is the weight of an external node $j$ , and $l_{j}$ is the distance from the root of the tree to $j$ . If $w_{j}=1$ for all $j$ , then weighted path length is exactly the same as external path length. Example Let $T$ be the following extended binary tree. Square nodes are external nodes, and circular nodes are internal nodes. Values in external nodes indicate weights, which are given in this problem, while values in internal nodes represent the weighted path length of subtrees rooted at those nodes, and are calculated from the given weights and the given tree. The weight of the tree as a whole is given at the root of the tree. This tree happens to give the minimum weighted path length for this particular set of weights.
随便看	HamiltonianGraph Hamiltonian graph HamiltonianGroup Hamiltonian group HamiltonianOperator Hamiltonian operator HamiltonianPath Hamiltonian path HamiltonianQuaternions Hamiltonian quaternions HamiltoniantypeEllipticSystem Hamiltonian-type elliptic system HamiltonianVectorField Hamiltonian vector field HammingDistance Hamming distance HammingMetric Hamming metric HamSandwichTheorem ham sandwich theorem HandleDecomposition handle decomposition HandshakeLemma handshake lemma HankelContourIntegral