#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define int ll
using namespace std;
ll sz[200009], ma[200009], pre[200009], i, m, n, u, v, ans[200009], check[200009], maxdepth;
vector<int> g[200009];
// DFS để tính kích thước các cây con
void dfs(int id, int par) {
sz[id] = 1;
for (int x : g[id]) {
if (x == par || check[x]) continue;
dfs(x, id);
sz[id] += sz[x];
}
}
// Tìm centroid của cây
int centroid(int id, int par, int siz) {
for (int u : g[id]) {
if (u == par || check[u]) continue;
if (sz[u] * 2 >= siz) return centroid(u, id, siz);
}
return id;
}
// DFS để tính độ sâu và giá trị lớn nhất
void dfs2(int id, int par, int h) {
maxdepth = max(maxdepth, sz[id]); // Sửa lại từ sz[u] thành sz[id]
ma[sz[id]] = max(ma[sz[id]], h);
for (int u : g[id]) {
if (u == par || check[u]) continue;
dfs2(u, id, h + 1);
}
}
// Xử lý từng centroid
void solve(int id) {
// Bước 1: Tính kích thước cây con
dfs(id, 0);
int c = centroid(id, 0, sz[id]); // Tìm centroid của cây
check[c] = 1; // Đánh dấu centroid là đã xử lý
// Bước 2: Tính lại kích thước sau khi xác định centroid
dfs(c, 0);
// Bước 3: Tính toán giá trị lớn nhất dựa trên các cây con của centroid
maxdepth = 0;
for (int u : g[c]) {
if (check[u]) continue;
dfs2(u, c, 2);
for (int i = sz[u] - 1; i >= 1; i--) ma[i] = max(ma[i], ma[i + 1]);
for (int i = sz[u]; i >= 1; i--) {
ans[i * 2] = max(ans[i * 2], ma[i]);
ans[i * 2] = max(ans[i * 2], ma[i] + pre[i] - 1);
pre[i] = max(pre[i], ma[i]);
}
// Đặt lại mảng `ma[]` sau mỗi cây con
for (int i = 1; i <= sz[u]; i++) ma[i] = 0;
}
// Đặt lại các giá trị `pre[]` và `ma[]` sau khi tính toán cho các cây con
for (int i = 1; i <= maxdepth; i++) pre[i] = 0, ma[i] = 0;
// Bước 4: Xử lý đệ quy với các cây con của centroid
for (int u : g[c]) {
if (check[u]) continue;
solve(u);
}
}
signed main() {
if (fopen(taskname ".inp", "r")) {
freopen(taskname ".inp", "r", stdin);
freopen(taskname ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (i = 1; i < n; i++) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
// Gọi hàm xử lý từ node 1
solve(1);
// In kết quả
for (i = 1; i <= n; i++) {
if (i & 1) cout << 1 << "\n";
else cout << ans[i] << "\n";
}
return 0;
}
Compilation message
meetings2.cpp: In function 'int main()':
meetings2.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | freopen(taskname ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(taskname ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
10832 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
10832 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10832 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
10832 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
