In programming lingo a tree is usually a directed acyclic graph in which every node has exactly one incoming edge (one parent) except for the root node, which has no parents. A "cycle" in a directed graph is a loop that connects a node to itself along directed edges, so "acyclic" just means there aren't any loops. In this case, that means no circular dependencies among the computations.
There's also a mathematical definition of tree which is occasionally used in theoretical CS, so you have to be careful about getting them mixed up, but that kind of tree is an undirected acyclic graph. The kind of tree they're talking about in the article is directed, because it represents computational dependencies. (If A is connected to B, then either A depends on B or B depends on A. The dependency only goes one way.)
The defining difference between a tree and a directed acyclic graph is that a node in a DAG can have more than one incoming edge. So a DAG is like a tree in which nodes can have more than one parent. Here's the simplest illustration. I can't draw arrows, but imagine each edge being directed from top to bottom, so that A is the root of the tree:
A (a tree, therefore A (a DAG, but not a tree)
/ \ also a DAG ) / \
B C B C
/ \ /
D D
In the tree, D can have only one incoming edge (only one parent) so there can only be one path from A to D along the directed edges. In the DAG, D can have multiple incoming edges (from B and C in this case) so there can be multiple paths from A to D. Direction is important to keep in mind (and I really wish I could draw it.) Note that in the DAG, A-B-D-C-A isn't a loop because D-C-A goes against the direction of the edges: A->B->D<-C<-A. Also note that if the tree were not directed, it would be useless for representing dependencies, because it would not tell us whether C depends on A and D, or D depends on C and A depends on C, or maybe D depends on C which depends on A which depends on B. The order of the edges is what tells us that A depends on C and not vice-versa.
Here's what the article means by converting a tree into a DAG for computation. In the following illustration, I'm going to use letters to label the nodes, but different nodes in the same graph are different, even if they have the same label. Here's the tree:
A
/ \
B C
/ / \
D E D
\ \
F F
Suppose the node labels represent computations, and the edges represent dependencies. A depends on the results of B and C, B depends on the result of D, C depends on the results of E and D, and D depends on the result of F. If you perform all the computations as they are represented in this tree, D and F will be computed twice. This might be inefficient. So you take nodes with the same labels and identify them, make them the same. That gives you a different graph which is no longer a tree:
A
/ \
B C
\ / \
D E
\
F
This DAG represents the same dependencies that the tree above does, and since nodes with identical labels have been combined, each computation is represented once. The tree representation is easier to create, because you don't have to worry about finding and combining duplicate nodes, but the DAG is more efficient to compute.
The idea of memoization is that each node in the tree should be the name of a computation, and the computation itself should be looked up by name. That way even if a name occurs multiple times in the tree, the computation it names will only occur once. The computations named "B" and "C" both depend on a computation named "D" which they will look up by name. They don't have to know they share a dependency, and they don't even have to reference the same copy of the name "D". This extra layer of indirection is the "black box of memoization" that implicitly turns the tree into a DAG to avoid replicating computations D and F.
I should add: a consequence of allowing more than one incoming edge is that a DAG can have more than one "root," like this:
A B
\ /
C
With trees, if you have two roots, you'll have two disjoint trees, because there's no way for their descendants to meet without some node having multiple parents.
There's also a mathematical definition of tree which is occasionally used in theoretical CS, so you have to be careful about getting them mixed up, but that kind of tree is an undirected acyclic graph. The kind of tree they're talking about in the article is directed, because it represents computational dependencies. (If A is connected to B, then either A depends on B or B depends on A. The dependency only goes one way.)
The defining difference between a tree and a directed acyclic graph is that a node in a DAG can have more than one incoming edge. So a DAG is like a tree in which nodes can have more than one parent. Here's the simplest illustration. I can't draw arrows, but imagine each edge being directed from top to bottom, so that A is the root of the tree:
In the tree, D can have only one incoming edge (only one parent) so there can only be one path from A to D along the directed edges. In the DAG, D can have multiple incoming edges (from B and C in this case) so there can be multiple paths from A to D. Direction is important to keep in mind (and I really wish I could draw it.) Note that in the DAG, A-B-D-C-A isn't a loop because D-C-A goes against the direction of the edges: A->B->D<-C<-A. Also note that if the tree were not directed, it would be useless for representing dependencies, because it would not tell us whether C depends on A and D, or D depends on C and A depends on C, or maybe D depends on C which depends on A which depends on B. The order of the edges is what tells us that A depends on C and not vice-versa.Here's what the article means by converting a tree into a DAG for computation. In the following illustration, I'm going to use letters to label the nodes, but different nodes in the same graph are different, even if they have the same label. Here's the tree:
Suppose the node labels represent computations, and the edges represent dependencies. A depends on the results of B and C, B depends on the result of D, C depends on the results of E and D, and D depends on the result of F. If you perform all the computations as they are represented in this tree, D and F will be computed twice. This might be inefficient. So you take nodes with the same labels and identify them, make them the same. That gives you a different graph which is no longer a tree: This DAG represents the same dependencies that the tree above does, and since nodes with identical labels have been combined, each computation is represented once. The tree representation is easier to create, because you don't have to worry about finding and combining duplicate nodes, but the DAG is more efficient to compute.The idea of memoization is that each node in the tree should be the name of a computation, and the computation itself should be looked up by name. That way even if a name occurs multiple times in the tree, the computation it names will only occur once. The computations named "B" and "C" both depend on a computation named "D" which they will look up by name. They don't have to know they share a dependency, and they don't even have to reference the same copy of the name "D". This extra layer of indirection is the "black box of memoization" that implicitly turns the tree into a DAG to avoid replicating computations D and F.