So, I read the topcoder analysis, and their solution is really nice.
We'll use Example 1 to illustrate. Here is how my DFS defined the two trees (edges going from the lower nodes to the higher nodes):
![]() |
![]() |
Parent PointersNode 0 1 2 3 4 T1 -1 2 0 0 1 T2 -1 0 4 4 1 |
T1: 4 1 2 3 0 T2: 2 3 4 1 0
Next, you OR node i's vector with its parents. That's how you get the sets right for the parents.
Below, I'll go through the whole process for T1. For each node that we process (which defines an edge that separates the tree into two components), I'll draw the trees, and identify the two sets as yellow (set A) and green (set B). I'll include the bit representation of the sets, both as bits and as hex.
I'm also coloring the sets when they change -- red means that that is the final set specification for the node, and blue means that this was the parent of a node that changed.
Node | Edge | Graph | Set for 0 | Set for 1 | Set for 2 | Set for 3 | Set for 4 |
Start | Start | ![]() |
00000 0x00 | 00000 0x00 | 00000 0x00 | 00000 0x00 | 00000 0x00 |
4 | 4->1 | ![]() |
00000 0x00 | 10000 0x10 | 00000 0x00 | 00000 0x00 | 10000 0x10 |
1 | 1->2 | ![]() |
00000 0x00 | 10010 0x12 | 10010 0x12 | 00000 0x00 | 10000 0x10 |
2 | 2->0 | ![]() |
10110 0x16 | 10010 0x12 | 10110 0x16 | 00000 0x00 | 10000 0x10 |
3 | 3->0 | ![]() |
11110 0x1e | 10010 0x12 | 10110 0x16 | 01000 0x8 | 10000 0x10 |
You'll note, we don't process node 0, because it's the root, and has no parent pointers.
Now, we're going to traverse each node/edge of T2, also in topological order, and we're going to partition the nodes into two sets, C and D. Before we begin, all of the nodes are in C.
We store two values during the traversal:
Now, for each node/edge in T2, we are going to maintain two values:
Calculate the biggest of these, square it, and add it to the total.
T1's Node |
T1's Edge |
T1's Graph |
The set | AC | BC | T2's Node |
T2's Edge |
T2's Graph |
AD[n] | BD[n] | |AIC| | |AID| | |BIC| | |BID| | Similarity |
4 | 4->1 | ![]() |
10000 0x10 | 4 | 1 | 2 | 2->4 | ![]() |
1 | 0 | 3 | 1 | 1 | 0 | 9 |
4 | 4->1 | ![]() |
10000 0x10 | 4 | 1 | 3 | 3->4 | ![]() |
1 | 0 | 3 | 1 | 1 | 0 | 9 |
4 | 4->1 | ![]() |
10000 0x10 | 4 | 1 | 4 | 4->1 | ![]() |
2 | 1 | 2 | 2 | 0 | 1 | 4 |
4 | 4->1 | ![]() |
10000 0x10 | 4 | 1 | 1 | 1->0 | ![]() |
3 | 1 | 1 | 3 | 0 | 1 | 9 |
1 | 1->2 | ![]() |
10010 0x12 | 3 | 2 | 2 | 2->4 | ![]() |
1 | 0 | 2 | 1 | 2 | 0 | 4 |
1 | 1->2 | ![]() |
10010 0x12 | 3 | 2 | 3 | 3->4 | ![]() |
1 | 0 | 2 | 1 | 2 | 0 | 4 |
1 | 1->2 | ![]() |
10010 0x12 | 3 | 2 | 4 | 4->1 | ![]() |
2 | 1 | 1 | 2 | 1 | 1 | 4 |
1 | 1->2 | ![]() |
10010 0x12 | 3 | 2 | 1 | 1->0 | ![]() |
2 | 2 | 1 | 2 | 0 | 2 | 4 |
And so on.