Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the right place to ask the question. Let me know if it should be asked somewhere else.

I will explain the problem below but raise the question at this point. Is there any terminology I should be aware of which could clarify the problem below? Is the problem similar to any known problem? Perhaps it already has a name? If not, do you see if there is any part of the description below which is a known problem?


Let $A$ and $B$ both be trees where each node is a set of labels. Let $f$ be a function which given a tree and a node in the tree calculates a value. It is known that the value of an ancestor is the sum of its children.

I am given the values of $f$ for the nodes in $A$. The problem is to compute the values for nodes in $B$.

Let $a$ and $b$ be a node in $A$ and $B$, respectively; we have the following cases: 1. labels($a$) = labels($b$) 2. labels($a$) is a proper subset of labels($b$) 3. labels($b$) is a proper subset of labels($a$) 4. labels($a$) is disjoint of labels($b$)

A node $b$ in case 1 would just have its value set to the value of node $a$.

If an ancestor in $b$ has all its children set, then the ancestor can be calculated by summing the children.

In case 2, we know that node $b$ is at least the value of $a$; if we find nodes in $A$ so that they together are exactly the set of labels in $b$, then we can set $b$ to the sum of these nodes.

In case 3, we could attempt to set the value to $a$, and then hope to find how much we need to deduct. If we can find values for these set of labels: labels($b$) difference labels($a$), then we can deduct the sum of those values and get the value of node $b$.

share|improve this question

migrated from cstheory.stackexchange.com Apr 27 '11 at 4:03

This question came from our site for theoretical computer scientists and researchers in related fields.

There seems to be a contradiction here between two different kinds of additivity. You specify that the value of $f$ at a node is the sum of the values of $f$ at its children. That completely determines the function values at the non-leaf nodes. However, in discussing cases 2 and 3, you seem to be assuming, if I understand correctly, that the value of $f$ at a node is also the sum of values corresponding to the individual labels. These two additivities together would overdetermine the values of $f$ at the non-leaf nodes, unless there are constraints on the labels forcing them to be compatible. –  joriki Apr 27 '11 at 4:39
This reminds me a little bit of a Huffman tree -- the "frequency value" of each non-leaf node in that tree is the sum of the "frequency value" of both of its immediate children, and it is also equal to the sum of all the "frequency values" of every leaf directly or indirectly descended from that non-leaf node. –  David Cary Dec 10 '11 at 6:51
This reminds me a little bit of some implementations of the rope data structure, where each non-leaf node stores pointers to the left-part and the right-part of the string it represents, and also stores the weight of the "string" it represents (the total of the weight of the left-part and the right-part), and several different ropes can share some of their leaves and (in some cases) a few of their non-leaf nodes. –  David Cary Dec 10 '11 at 7:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.