subtree.js

var _ = require('underscore');
var BigNumber = require('bignumber.js');

/////// tree //////////

function Node(data, weight) {
    this.data = data;
    this.weight = weight;
    this.parent = null;
    this.children = [];
    this.depth = 0;
}
 
function Tree(data, weight, orNode) {
	var node;
	if (orNode) {
		node = orNode;
	} else {
		node = new Node(data, weight);
	}
    this._root = node;
}
 
Tree.prototype.DFS = function(callback) {
    (function recurse(currentNode) {
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            recurse(currentNode.children[i]);
        }
        callback(currentNode);
    })(this._root);
};

Tree.prototype.BFS = function(callback) {
    var queue = [];
    queue.push(this._root);
    currentTree = queue.pop();
 
    while(currentTree){
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.push(currentTree.children[i]);
        }
 
        callback(currentTree);
        currentTree = queue.pop();
    }
};
 
Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};
 
Tree.prototype.add = function(data, weight, toData, traversal) {
    var child = new Node(data, weight),
        parent = null,
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        }; 
    this.contains(callback, traversal);
    if (parent) {
        parent.children.push(child);
        child.parent = parent;
        child.depth = parent.depth + 1;
    }
};
 
Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;
 
    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };
    this.contains(callback, traversal);
    if (parent) {
        index = findIndex(parent.children, data);
        childToRemove = parent.children.splice(index, 1);
    } 
    return childToRemove;
};
 
function findIndex(arr, data) {
    var index;
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }
    return index;
}

////// tree ///////

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
	input_stdin += data;
});

process.stdin.on('end', function () {
	input_stdin_array = input_stdin.split("\n");
	main();    
});

function readLine() {
	return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
	var size = parseInt(readLine());

	for (var i=0; i<size; ++i) {
		var numOfVertices = parseInt(readLine());
		var weightsOfVertices = readLine().split(' ').map(Number);
		var aVals = readLine().split(' ').map(Number);
		
		var tree = genTree(numOfVertices-1, weightsOfVertices);
		var subTreeWeights = getSubtreeWeights(tree, weightsOfVertices);
		calculate(subTreeWeights, aVals);
	}

	function genTree(edges, weights) {
		var tree = null;

		for (var i=0; i<edges; ++i) {
			var vertsToConnect = readLine().split(' ').map(Number);
			var vert1 = vertsToConnect[0],
				vert2 = vertsToConnect[1];

				if (tree === null) {
					tree = new Tree(vert1, weights[vert1-1]);
				}

			tree.add(vert2, weights[vert2-1], vert1, tree.DFS);
		}

		return tree;
	}

	function getSubtreeWeights(tree, weights) {
		var results = [];

		var memo = {};
		
		tree.DFS(function(node) {
			var stack = [];
			var substack = [];
			var superstack = [];
			
			var temp = new Tree(null, null, node);
			// console.log(node.data);
			
			temp.BFS(function(subnode) {
				var RFM = null;
				// console.log('\t', subnode.data, node.depth, subnode.depth);
				if (subnode.data in memo) {
					if (node.depth === subnode.depth - 1) {
						RFM = prefixSub([node.data, node.depth], memo[subnode.data]);
					} 
				} else {
					if (substack.length > 0) {
						while (substack[substack.length-1][1] >= subnode.depth) {
							substack.pop();
						}
					}

					substack.push([subnode.data, subnode.depth]);
					// console.log('\t', substack);
					stack.push(JSON.parse(JSON.stringify(substack)));
				}				

				if (RFM !== null) {
					// console.log('\t\tRFM', RFM);
					RFM.forEach(function(x) {
						stack.push(JSON.parse(JSON.stringify(x)));
					});
				} else {
					// console.log('\t\tSS', substack);
				}

				superstack.push([subnode.data, subnode.depth]);

			});
				
			stack.push(JSON.parse(JSON.stringify(superstack)));

			// save subtrees for node
			memo[node.data] = JSON.parse(JSON.stringify(stack));

			// console.log(stack);
			var clean = cleanup(stack);
			console.log(clean);

			for (var i=0; i<clean.length; i++) {
				var sum = 0;
				for (var j=0; j<clean[i].length; j++) {
					sum += weights[clean[i][j]-1];
				}
				results.push(sum);
			}
		});
		console.log(results);

		return results;
	}

	function cleanup(stack) {
		var clean = [];
		for (var i=0; i<stack.length; i++) {
			var sub = [];
			for (var j=0; j<stack[i].length; j++) {
				sub.push(stack[i][j][0]);
			}
			clean.push(sub);
		}

		var hash = {};
		var out = [];
		for (var i = 0, l = clean.length; i < l; i++) {
			var key = clean[i].join('|');
			if (!hash[key]) {
				out.push(clean[i]);
				hash[key] = 'found';
			}
		}

		return out;
	}

	function calculate(subTreeWeights, aVals){
		var total = 0;
		subTreeWeights.forEach(function(w){
			total += aVals[w];
		});

		var cal = (total * 1.0)/(subTreeWeights.length);
		console.log(cal.toPrecision(5));
		// console.log(cal);
	}

	function prefixSub(pre, subtrees) {
		for (var i=0; i<subtrees.length; i++) {
			subtrees[i].unshift(pre);
		}

		return subtrees;
	}
}