Hướng dẫn giải của [Beginner Free Contest 05] TREE
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.
Hướng dẫn giải
Cho ~A_u~ là khoảng cách từ ~u~ tới đỉnh xa nhất (độ lệch tâm). Hỏi có tồn tại cây ~N~ đỉnh có đúng dãy độ lệch tâm đó (đỉnh đánh nhãn tùy ý) hay không.
Sub 1: Vét cạn — dùng khi ~N \le 8~
Duyệt mọi cây có nhãn bằng mã Prüfer (~N^{N-2}~ cây), tính độ lệch tâm mỗi đỉnh bằng Floyd, sắp xếp rồi so với dãy ~A~ đã sắp xếp. Nếu chỉ nộp sub này: đúng 5/45 test.
Sub 2: Điều kiện theo đường kính — ~O(N)~
Gọi ~D = \max A~ là đường kính, ~m = \lceil D/2 \rceil~. Độ lệch tâm của đỉnh ~v~ bằng ~m~ cộng khoảng cách tới tâm. Do đó: không có giá trị nhỏ hơn ~m~; có đúng 1 giá trị ~m~ nếu ~D~ chẵn (một tâm), đúng 2 nếu ~D~ lẻ (hai tâm kề nhau); mọi giá trị từ ~m+1~ đến ~D-1~ xuất hiện ít nhất một lần (mỗi độ sâu có đỉnh); giá trị ~D~ xuất hiện ít nhất 2 lần (hai nhánh dài nhất). Các điều kiện này cũng đủ vì đỉnh thừa luôn treo được vào đúng độ sâu của mình. Nếu chỉ nộp sub này: đúng 45/45 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~N \le 8~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
// Sub 1: vét cạn mọi cây (mã Prüfer), dùng khi n <= 8
// Gán nhãn đỉnh tùy ý nên chỉ cần so sánh dãy độ lệch tâm đã sắp xếp.
void sub1() {
vector<int> target(a + 1, a + n + 1);
sort(target.begin(), target.end());
bool ok = false;
auto check = [&](vector<pair<int,int>>& edges) {
vector<vector<int>> d(n, vector<int>(n, 1000));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (auto& e : edges) d[e.first][e.second] = d[e.second][e.first] = 1;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
vector<int> ecc(n);
for (int i = 0; i < n; i++) ecc[i] = *max_element(d[i].begin(), d[i].end());
sort(ecc.begin(), ecc.end());
if (ecc == target) ok = true;
};
if (n == 1) {
vector<pair<int,int>> e;
check(e);
} else if (n == 2) {
vector<pair<int,int>> e = {{0, 1}};
check(e);
} else {
int len = n - 2;
vector<int> pr(len, 0);
while (!ok) {
// dựng cây từ mã Prüfer
vector<int> deg(n, 1);
for (int x : pr) deg[x]++;
vector<pair<int,int>> e;
vector<int> dg = deg;
for (int x : pr) {
for (int v = 0; v < n; v++)
if (dg[v] == 1) { e.push_back({v, x}); dg[v]--; dg[x]--; break; }
}
vector<int> rest;
for (int v = 0; v < n; v++) if (dg[v] == 1) rest.push_back(v);
e.push_back({rest[0], rest[1]});
check(e);
int i = len - 1;
while (i >= 0 && pr[i] == n - 1) pr[i--] = 0;
if (i < 0) break;
pr[i]++;
}
}
puts(ok ? "Possible" : "Impossible");
}
// Sub 2: điều kiện cần và đủ dựa trên đường kính D = max(A), O(N)
void sub2() {
vector<int> cnt(n + 2, 0);
int D = 0;
for (int i = 1; i <= n; i++) { cnt[a[i]]++; D = max(D, a[i]); }
bool ok = true;
// m = độ lệch tâm nhỏ nhất = ceil(D/2); các đỉnh có A < m là không thể
int m = (D + 1) / 2;
for (int v = 0; v < m; v++) if (cnt[v] > 0) ok = false;
if (D % 2 == 0) { if (cnt[m] != 1) ok = false; } // một tâm duy nhất
else { if (cnt[m] != 2) ok = false; } // đúng hai tâm kề nhau
for (int v = m + 1; v < D; v++) if (cnt[v] < 1) ok = false; // mỗi độ sâu phải có đỉnh
if (D > m && cnt[D] < 2) ok = false; // hai nhánh dài nhất
if (n == 1) ok = (a[1] == 0);
puts(ok ? "Possible" : "Impossible");
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
if (n <= 8) sub1();
else sub2();
return 0;
}
Bình luận