Kotlin | Rust
\n\nhttps://youtu.be/Y4Uurs3uKVE\n\n#### Join me on Telegram\n\nhttps://t.me/leetcode_daily_unstoppable/780\n\n#### Problem TLDR\n\nn new heights by cutting nod
![1.webp](https://assets.leetcode.com/users/images/582963a7-b115-439c-b1a0-6dc880f19e35_1729933949.7827187.webp)\n\nhttps://youtu.be/Y4Uurs3uKVE\n\n#### Join me on Telegram\n\nhttps://t.me/leetcode_daily_unstoppable/780\n\n#### Problem TLDR\n\n`n` new heights by cutting nodes in a Tree #hard #dfs\n\n#### Intuition\n\nAfter cut, check the sibling: if it has the bigger depth, we are good, otherwise update and go up. This will take O(log(n)) for each call.\n\nWe can speed it up by tracking the `level` from the node to upwards the root.\n\n\nThe catch is the siblings of each level: there are can be more than one of them. Check if cutting node is the current level maximum depth, and if so, take the second maximum of the depth.\n\n#### Approach\n\n* can be done in a single DFS traversal\n* in Rust `let m = ld[lvl]` makes a `copy`, do `&mut ld[lvl]` instead (silent bug) \n* arrays are faster than HashMap (in the leetcode tests runner)\n\n#### Complexity\n\n- Time complexity:\n$$O(n + q)$$\n\n- Space complexity:\n$$O(n + q)$$\n\n#### Code\n\n```kotlin []\n\n    fun treeQueries(root: TreeNode?, queries: IntArray): IntArray {\n        val lToD = Array(100001) { intArrayOf(-1, -1) }; val vToLD = lToD.clone()\n        fun dfs(n: TreeNode?, lvl: Int): Int = n?.run {\n            val d = 1 + max(dfs(left, lvl + 1), dfs(right, lvl + 1))\n            vToLD[`val`] = intArrayOf(lvl, d); val m = lToD[lvl]\n            if (d > m[0]) { m[1] = m[0]; m[0] = d } else m[1] = max(m[1], d); d\n        } ?: -1\n        dfs(root, 0)\n        return IntArray(queries.size) { i ->\n            val (lvl, d) = vToLD[queries[i]]; val (d1, d2) = lToD[lvl]\n            lvl + if (d < d1) d1 else d2\n        }\n    }\n\n```\n```rust []\n\n    pub fn tree_queries(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<i32> {\n        type D = [(i32, i32); 100001]; \n        let mut ld = [(-1, -1); 100001]; let mut vld = ld.clone();\n        fn dfs(ld: &mut D, vld: &mut D, n: &Option<Rc<RefCell<TreeNode>>>, lvl: i32) -> i32 {\n            let Some(n) = n else { return -1 }; let mut n = n.borrow_mut();\n            let d = 1 + dfs(ld, vld, &n.left, lvl + 1).max(dfs(ld, vld, &n.right, lvl + 1));\n            vld[n.val as usize] = (lvl, d); let m = &mut ld[lvl as usize];\n            if d > m.0 { m.1 = m.0; m.0 = d } else { m.1 = m.1.max(d) }; d\n        }\n        dfs(&mut ld, &mut vld, &root, 0);\n        queries.iter().map(|&q| { \n          let (lvl, d) = vld[q as usize]; let (d1, d2) = ld[lvl as usize]; \n            lvl + if d < d1 { d1 } else { d2 }}).collect()\n    }\n\n```\n```c++ []\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        array<pair<int, int>, 100001> ld{}, vld = ld;\n        function<int(TreeNode*,int)> f = [&](TreeNode* n, int l) {\n            if (!n) return 0;\n            int d = 1 + max(f(n->left, l + 1), f(n->right, l + 1));\n            vld[n->val] = {l, d}; auto& [d1, d2] = ld[l];\n            if (d > d1) d2 = d1, d1 = d; else d2 = max(d2, d);\n            return d;\n        };\n        f(root,0);\n        transform(begin(queries), end(queries), begin(queries), [&](int q){\n            auto [l, d] = vld[q]; auto [d1, d2] = ld[l]; return l - 1 + (d < d1 ? d1 : d2);\n        });\n        return queries;\n    }\n\n```
['Breadth-First Search', 'C++', 'Rust', 'Kotlin']