We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Data Structures
- Trees
- Balanced Forest
- Discussions
Balanced Forest
Balanced Forest
Sort by
recency
|
76 Discussions
|
Please Login in order to post a comment
For C++11, remember the change also the result type in the main function. Not just your solution function. What a joke
hard question
O(n log(n)), requires 3 pass over the tree, 1st to construct it, 2nd to calculate total sum of each subtree, 3rd to find the suitable partitions
dont know if there's a O(n) algo
Everyone can try to solve by this js code
function addChild(tree, c, node, child) { tree[node] = tree[node] ?? { children: new Set(), val: c[node - 1] }; tree[node].children.add(child); }
function cleanUpTree(tree, node = 1, parent = -1, vMap = {}) { let { children, val } = tree[node]; children.delete(parent); for (const child of children) { const [v] = cleanUpTree(tree, child, node, vMap); val += v; } vMap[val] = (vMap[val] ?? 0) + 1; tree[node].val = val; return [val, vMap]; }
function getMin(a, b) { return a === -1 || a > b ? b : a; }
function* dfsIter(tree, vMap, node = 1, parentVMap = {}) { const { val, children } = tree[node]; vMap[val]--; parentVMap[val] = (parentVMap[val] ?? 0) + 1; for (const child of children) yield* dfsIter(tree, vMap, child, parentVMap); parentVMap[val]--; if (node === 1) return; yield [val, parentVMap]; }
function balancedForest(c, edges) { let ret = -1; if (!c?.length || !edges?.length) return ret;
}
js
WTF. It took me an entire noon to figure it out and ultimately I found that in C++, the data type of the variable used to receive the answer is INT. However, some answers of examples exceed 2^31 - 1. It should be LONG. Damn.