Smallest Missing Genetic Value in Each Subtree (LeetCode 2003)
Đề bài
LeetCode 2003 – Smallest Missing Genetic Value in Each Subtree (Giá trị gen nhỏ nhất bị thiếu trong mỗi cây con) – độ khó Hard.
Có một cây gia phả có gốc là nút $0$, gồm $n$ nút được đánh số từ $0$ đến $n - 1$. Cho mảng số nguyên parents (đánh số từ 0), trong đó parents[i] là cha của nút $i$. Vì nút $0$ là gốc nên parents[0] == -1.
Có $10^5$ giá trị gen, mỗi giá trị được biểu diễn bằng một số nguyên trong đoạn $[1, 10^5]$ (tính cả hai đầu). Cho mảng số nguyên nums (đánh số từ 0), trong đó nums[i] là giá trị gen của nút $i$, các giá trị này đôi một khác nhau.
Yêu cầu: trả về mảng ans độ dài $n$, trong đó ans[i] là giá trị gen nhỏ nhất bị thiếu trong cây con có gốc tại nút $i$.
Cây con có gốc tại nút $x$ gồm nút $x$ và tất cả các nút con cháu của nó.
Ràng buộc:
n == parents.length == nums.length- $2 \le n \le 10^5$
- $0 \le$
parents[i]$\le n - 1$ với $i \ne 0$ parents[0] == -1parentsbiểu diễn một cây hợp lệ.- $1 \le$
nums[i]$\le 10^5$ - Các
nums[i]đôi một khác nhau.
Ví dụ 1:
Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]Giải thích: đáp án cho từng cây con như sau:
- 0: cây con gồm các nút [0,1,2,3] với các gen [1,2,3,4]. Giá trị nhỏ nhất bị thiếu là 5.
- 1: cây con chỉ gồm nút 1 với gen 2. Giá trị nhỏ nhất bị thiếu là 1.
- 2: cây con gồm các nút [2,3] với các gen [3,4]. Giá trị nhỏ nhất bị thiếu là 1.
- 3: cây con chỉ gồm nút 3 với gen 4. Giá trị nhỏ nhất bị thiếu là 1.
Ví dụ 2:
Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]Giải thích:
- 0: cây con gồm các nút [0,1,2,3,4,5] với các gen [5,4,6,2,1,3]. Giá trị nhỏ nhất bị thiếu là 7.
- 1: cây con gồm các nút [1,2] với các gen [4,6]. Giá trị nhỏ nhất bị thiếu là 1.
- 2: cây con chỉ gồm nút 2 với gen 6. Giá trị nhỏ nhất bị thiếu là 1.
- 3: cây con gồm các nút [3,4,5] với các gen [2,1,3]. Giá trị nhỏ nhất bị thiếu là 4.
- 4: cây con chỉ gồm nút 4 với gen 1. Giá trị nhỏ nhất bị thiếu là 2.
- 5: cây con chỉ gồm nút 5 với gen 3. Giá trị nhỏ nhất bị thiếu là 1.
Ví dụ 3:
Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]Giải thích: giá trị 1 bị thiếu trong tất cả các cây con.
2003. Smallest Missing Genetic Value in Each Subtree – Hard
There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.
There are $10^5$ genetic values, each represented by an integer in the inclusive range $[1, 10^5]$. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.
Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.
The subtree rooted at a node x contains node x and all of its descendant nodes.
Example 1:
Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.Example 2:
Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.Example 3:
Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]
Explanation: The value 1 is missing from all the subtrees.Constraints:
n == parents.length == nums.length- $2 \le n \le 10^5$
- $0 \le$
parents[i]$\le n - 1$ fori != 0 parents[0] == -1parentsrepresents a valid tree.- $1 \le$
nums[i]$\le 10^5$ - Each
nums[i]is distinct.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Nói trước với các bạn là bài này mình không đảm bảo cách làm của mình là tối ưu nhất. Mấu chốt để cách làm của mình AC được là nhờ vào một cấu trúc dữ liệu có sẵn của GNU C++ là ordered_set (thư viện pb_ds), chứ ban đầu mình bị TLE với một số test. Tuy nhiên mình có xem sơ qua code của một số người AC thì lại không cần dùng đến cấu trúc dữ liệu này như mình. Nên mình nói rõ để các bạn xem tham khảo được gì thì tham khảo hen. Ở cuối bài mình có trình bày thêm cách làm $O(n)$ mà nhiều bạn AC đã dùng để các bạn so sánh.
class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 là $n$, dòng 2 là $n$ số của parents, dòng 3 là $n$ số của nums; in ra $n$ số của mảng ans cách nhau dấu cách. Ví dụ 1 sẽ nhập là:4
-1 0 0 2
1 2 3 4Mình giải thích lại đề cho bạn nào chưa hiểu: mỗi nút của cây mang một số (gen), các số đôi một khác nhau. Với mỗi nút $i$, gom tất cả các số nằm trong cây con gốc $i$ lại thành một tập hợp, rồi tìm số nguyên dương nhỏ nhất không có trong tập đó (người ta hay gọi là MEX của tập). Ví dụ 2: cây con gốc 3 gồm các nút 3, 4, 5 mang các số $\{2, 1, 3\}$ ⇒ có đủ 1, 2, 3, thiếu 4 ⇒ ans[3] = 4. Cây con gốc 1 gồm $\{4, 6\}$ thiếu ngay số 1 ⇒ ans[1] = 1.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Gộp tập nhỏ vào tập lớn + ordered_set – O(n log² n)
Ý tưởng: mỗi nút giữ tập hợp các gen trong cây con của nó
Đại khái ý tưởng bài này là với mỗi nút $u$, dùng một tập hợp (set) S[u] để lưu trữ tập hợp các gen trên cây con gốc $u$. Ban đầu S[u] chỉ có đúng gen của chính nút $u$. Khi DFS tới nút $u$, xử lý xong các cây con $v$ của nó, ta sẽ đổ các phần tử từ S[v] vào S[u]. Đổ hết các con xong thì S[u] chính là tập gen của cây con gốc $u$, tiến hành tìm phần tử nhỏ nhất không xuất hiện trong tập hợp là xong.
Đổ khéo hơn: luôn đổ tập nhỏ vào tập lớn
Thì thực ra ta vẫn đổ, nhưng phải đổ khéo hơn: nếu kích thước tập hợp S[u] nhỏ hơn kích thước S[v] thì ta hoán đổi 2 tập hợp lại (S[u].swap(S[v]) chỉ đổi "ruột" 2 cây, mất $O(1)$), rồi mới đổ tập ít phần tử hơn vào tập nhiều phần tử hơn. Làm vậy sẽ không bị TLE, vì tổng số thao tác đổ sẽ không vượt quá $N \log N$.
Tìm số nhỏ nhất bị thiếu bằng ordered_set + chặt nhị phân
Sau khi đổ xong, ta cần tìm MEX của S[u]. Duyệt từ 1 lên thì lại chậm, nên mình dùng chặt nhị phân kết hợp với sức mạnh của ordered_set. Cấu trúc dữ liệu này là một set (cũng tự sắp xếp tăng dần, cũng insert, lower_bound như set thường) nhưng có hỗ trợ thêm việc tìm vị trí của phần tử trong set: order_of_key(x) trả về số phần tử nhỏ hơn $x$, trong $O(\log n)$.
Code của mình xử lý 3 trường hợp:
- Phần tử nhỏ nhất của
S[u]khác 1 ⇒ thiếu ngay số 1 ⇒ans[u] = 1. - Phần tử lớn nhất của
S[u]bằng đúng kích thước tập ⇒ các gen khác nhau, đều $\ge 1$, có $k$ số mà lớn nhất là $k$ ⇒ tập chính là $\{1, 2, \ldots, k\}$ ⇒ans[u] = k + 1. - Còn lại: chặt nhị phân trên đoạn $[1, size + 1]$. Với mỗi
mid, lấyvaluelà số nhỏ nhất trong tập mà $\ge$mid(lower_bound). Nếu thứ tự củavaluetrong tập (order_of_key(value) + 1) đúng bằngvaluenghĩa là đủ hết các số $1, 2, \ldots, value$, kết quả còn lớn hơn nữa ⇒ cần tìm trên đoạn lớn hơn. Còn nếu thứ tự mà nhỏ hơnvaluethì trướcvalueđã có số bị thiếu, mà các số từmidtớivalue - 1lại không có trong tập ⇒ kết quả $\le$mid: lưu kết quả làmid, tìm trên đoạn nhỏ hơn.
lo = 1, hi = 6.mid = 3: value = 3, thứ tự = 3 = value ⇒ đủ 1..3 ⇒ lo = 4.mid = 5: value = 5, thứ tự = 4 < 5 ⇒ thiếu ⇒ res = 5, hi = 4.mid = 4: value = lower_bound(4) = 5, thứ tự = 4 < 5 ⇒ res = 4, hi = 3. Dừng ⇒ đáp án 4.Em nhập cây (mảng parents và nums) rồi bấm Tiếp để xem DFS đi lên từ lá, đổ tập nhỏ vào tập lớn và tính đáp án cho từng nút. Dòng chữ nhỏ dưới mỗi nút là tập S[u] hiện tại:
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set S[100005];
vector<int> adj[100005];
vector<int> ans;
void dfs(int u, int father) {
for (int i = 0; i < (int) adj[u].size(); i++) {
int v = adj[u][i];
if (v == father) {
continue;
}
dfs(v, u);
if ((int) S[u].size() < (int) S[v].size()) {
S[u].swap(S[v]);
}
for (ordered_set::iterator it = S[v].begin(); it != S[v].end(); it++) {
S[u].insert(*it);
}
S[v].clear();
}
if (*S[u].begin() != 1) {
ans[u] = 1;
return;
}
ordered_set::iterator it = S[u].end();
it--;
if (*it == (int) S[u].size()) {
ans[u] = *it + 1;
return;
}
int lo = 1;
int hi = (int) S[u].size() + 1;
int res = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
ordered_set::iterator it = S[u].lower_bound(mid);
int value = *it;
if ((int) S[u].order_of_key(value) + 1 == value) {
lo = mid + 1;
}
else {
res = mid;
hi = mid - 1;
}
}
ans[u] = res;
}
class Solution {
public:
vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
int n = (int) nums.size();
ans.clear();
ans.resize(n);
for (int i = 0; i < n; i++) {
adj[i].clear();
S[i].clear();
}
for (int i = 1; i < n; i++) {
adj[i].push_back(parents[i]);
adj[parents[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
S[i].insert(nums[i]);
}
dfs(0, -1);
return ans;
}
};
int main() {
int n;
cin >> n;
vector<int> parents(n), nums(n);
for (int i = 0; i < n; i++) cin >> parents[i];
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
vector<int> res = sol.smallestMissingValueSubtree(parents, nums);
for (int i = 0; i < n; i++) cout << res[i] << " ";
return 0;
}import sys
from typing import List
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
n = len(nums)
children = [[] for _ in range(n)]
for i in range(1, n):
children[parents[i]].append(i)
# thứ tự DFS từ gốc 0 (không đệ quy để tránh tràn stack khi cây là đường thẳng)
order = [0]
for u in order:
order.extend(children[u])
S = [{nums[i]} for i in range(n)]
ans = [1] * n
for u in reversed(order): # con luôn được xử lý trước cha
mex = 1
for v in children[u]:
if len(S[u]) < len(S[v]): # đổ tập nhỏ vào tập lớn
S[u], S[v] = S[v], S[u]
S[u].update(S[v])
S[v] = None
mex = max(mex, ans[v]) # tập của u chứa tập của v nên mex(u) >= mex(v)
while mex in S[u]:
mex += 1
ans[u] = mex
return ans
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
parents = [int(x) for x in data[1:1 + n]]
nums = [int(x) for x in data[1 + n:1 + 2 * n]]
res = Solution().smallestMissingValueSubtree(parents, nums)
print(" ".join(map(str, res)))
main()Giải thích một số chỗ trong code:
- Hai dòng
#include <ext/pb_ds/...>và#define ordered_set ...là để dùng ordered_set của GNU, chỉ có trên trình biên dịch g++ (LeetCode, Codeforces... đều dùng được). - Các mảng
S,adj,anskhai báo toàn cục, mà LeetCode gọi hàm nhiều lần cho nhiều test trên cùng một chương trình, nên đầu hàmsmallestMissingValueSubtreephảiclearlại hết. S[u].swap(S[v])đổi nội dung 2 tập trong $O(1)$, sau đóS[v]luôn là tập nhỏ hơn, ta đổ nó vàoS[u]rồiclearđể giải phóng bộ nhớ.- Bản Python: Python không có sẵn ordered_set, nên mình dùng
setthường, vẫn đổ tập nhỏ vào tập lớn. Riêng bước tìm MEX dùng một nhận xét: tập của $u$ chứa tập của mọi con $v$ nênans[u]$\ge$ans[v]; ta bắt đầu từ $\max$ans[v]rồi tăng dần đến khi gặp số không có trong tập. Số lần tăng chỉ đáng kể trên các tổ tiên của nút mang gen 1 (các nút khác đáp án luôn là 1), nên tổng lại vẫn chỉ $O(n)$. Ngoài ra bản Python duyệt cây bằng vòng lặp thay cho đệ quy để không bị giới hạn độ sâu đệ quy.
dfs đệ quy sâu đúng bằng chiều cao cây, tệ nhất là $10^5$ tầng (cây đường thẳng). Trên LeetCode code này AC bình thường, nhưng mình chạy thử trên máy Linux với stack mặc định 8 MB thì test đường thẳng $n = 10^5$ bị lỗi tràn stack (thoát giữa chừng, không in gì); nâng stack lên (ulimit -s unlimited) thì chạy đúng. Bạn nào dùng code này ở chỗ khác thì lưu ý nhé.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$: mỗi gen chỉ nằm trong đúng một tập tại mỗi thời điểm, cộng thêm danh sách kề và ngăn xếp đệ quy.
- Thời gian: tổng số lần chèn khi đổ tập là $O(n \log n)$, mỗi lần chèn vào ordered_set mất $O(\log n)$ ⇒ $O(n \log^2 n)$. Bước chặt nhị phân ở mỗi nút có $O(\log n)$ vòng, mỗi vòng gọi
lower_bound,order_of_keymất $O(\log n)$ ⇒ cũng $O(n \log^2 n)$ cho cả cây.
Cách 2Chỉ đi trên đường từ nút mang gen 1 lên gốc – O(n)
Như mình nói ở đầu bài, code của nhiều người AC không cần tới ordered_set. Mấu chốt là một nhận xét rất đơn giản:
Đi từ $x$ lên gốc thì cây con sau luôn chứa cây con trước. Vậy ta dùng một mảng đánh dấu has[] các gen đã gặp và mảng visited[] các nút đã duyệt: tới nút $u$ trên đường đi, ta chỉ duyệt thêm những nút chưa thăm trong cây con của $u$ (phần cây con trước đó đã thăm rồi thì không duyệt lại), đánh dấu gen của chúng. Đáp án cũng không giảm khi đi lên, nên biến mex chỉ việc tăng dần từ giá trị cũ.
| Nút trên đường đi (ví dụ 2) | Nút duyệt thêm | Gen đã có | mex |
|---|---|---|---|
| 4 (gen 1) | 4 | {1} | 2 |
| 3 | 3, 5 | {1, 2, 3} | 4 |
| 0 | 0, 1, 2 | {1, 2, 3, 4, 5, 6} | 7 |
Các nút 1, 2, 5 không nằm trên đường đi nên đáp án là 1 ⇒ ans = [7, 1, 1, 4, 2, 1], đúng như đề.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
int n = (int) nums.size();
vector<int> ans(n, 1);
int node = -1;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) node = i;
}
if (node == -1) return ans; // không có gen 1: mọi cây con đều thiếu 1
vector<vector<int>> children(n);
for (int i = 1; i < n; i++) children[parents[i]].push_back(i);
vector<bool> visited(n, false); // nút đã được duyệt
vector<bool> has(100002, false); // gen đã xuất hiện
int mex = 1;
while (node != -1) { // đi ngược lên từ nút có gen 1
vector<int> st;
st.push_back(node);
while (!st.empty()) { // duyệt các nút chưa thăm trong cây con
int u = st.back();
st.pop_back();
if (visited[u]) continue;
visited[u] = true;
has[nums[u]] = true;
for (int v : children[u]) {
if (!visited[v]) st.push_back(v);
}
}
while (has[mex]) mex++;
ans[node] = mex;
node = parents[node];
}
return ans;
}
};
int main() {
int n;
cin >> n;
vector<int> parents(n), nums(n);
for (int i = 0; i < n; i++) cin >> parents[i];
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
vector<int> res = sol.smallestMissingValueSubtree(parents, nums);
for (int i = 0; i < n; i++) cout << res[i] << " ";
return 0;
}import sys
from typing import List
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
if 1 not in nums: # không có gen 1: mọi cây con đều thiếu 1
return ans
node = nums.index(1)
children = [[] for _ in range(n)]
for i in range(1, n):
children[parents[i]].append(i)
visited = [False] * n # nút đã được duyệt
has = [False] * (n + 2) # gen đã xuất hiện (chỉ cần tới n + 1)
mex = 1
while node != -1: # đi ngược lên từ nút có gen 1
st = [node]
while st: # duyệt các nút chưa thăm trong cây con
u = st.pop()
if visited[u]:
continue
visited[u] = True
if nums[u] <= n:
has[nums[u]] = True
for v in children[u]:
if not visited[v]:
st.append(v)
while has[mex]:
mex += 1
ans[node] = mex
node = parents[node]
return ans
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
parents = [int(x) for x in data[1:1 + n]]
nums = [int(x) for x in data[1 + n:1 + 2 * n]]
res = Solution().smallestMissingValueSubtree(parents, nums)
print(" ".join(map(str, res)))
main()Đánh giá độ phức tạp: mỗi nút được đánh dấu visited và đẩy vào ngăn xếp tối đa vài lần (mỗi cạnh một lần), biến mex chỉ tăng tối đa tới $n + 1$ ⇒ thời gian $O(n)$ (cộng thêm mảng has cỡ $10^5$), bộ nhớ $O(n)$. Cách này cũng duyệt bằng ngăn xếp tự quản lý nên không lo tràn stack.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét