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
|
74 Discussions
|
Please Login in order to post a comment
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.
The statement of this problem has some defects !!, the output can be >= 0, and the statement says that it is only > 0, in addition to that it is understood that it is to divide the tree into 3, and then add the node, however in fact, you can split it in 2, and create a new tree....
In my opinion, it is not very sportsmanly to have skeleton code, which will never work - the return second query for sample input 3 should be 759000000000, which is too big to fit in the
int32
return type in the signature