Hướng dẫn giải của [CSES 1674] Subordinates
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Một cách khác để phát biểu bài toán: Cho một cây có gốc và ta cần tìm, với mỗi đỉnh, số lượng đỉnh con trong cây con của nó.
Bài toán này có thể được giải bằng một lượt duyệt DFS (Depth-First Search). Số lượng cấp dưới được tính bằng cách cộng dồn câu trả lời của từng đỉnh con với số lượng đỉnh con đó.
#include <iostream>
#include <vector>
using namespace std;
const int N = 200001;
vector<int> g[N];
int subordinates[N];
void dfs(int node) {
for (int child : g[node]) {
dfs(child);
subordinates[node] += subordinates[child] + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
g[p].push_back(i);
}
dfs(1);
for (int i = 1; i <= n; ++i) {
cout << subordinates[i] << ' ';
}
cout << '\n';
}
Tài liệu tham khảo
Chương trình tham khảo
#include <iostream>
#include <vector>
using namespace std;
const int N = 200001;
vector<int> g[N];
int subordinates[N];
void dfs(int node) {
for (int child : g[node]) {
dfs(child);
subordinates[node] += subordinates[child] + 1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
g[p].push_back(i);
}
dfs(1);
for (int i = 1; i <= n; ++i) {
cout << subordinates[i] << ' ';
}
cout << '\n';
}
Bình luận