제출 #496230

#제출 시각아이디문제언어결과실행 시간메모리
496230RainbowbunnyMeetings 2 (JOI21_meetings2)C++17
100 / 100
821 ms26772 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; int n; int sz[MAXN], ans[MAXN], H[MAXN], nw[MAXN]; bool Mark[MAXN]; vector <int> Adj[MAXN]; void DFS(int node, int p) { sz[node] = 1; for(auto x : Adj[node]) { if(x == p or Mark[x]) { continue; } DFS(x, node); sz[node] += sz[x]; } } int FindCen(int node, int p, int cursz) { for(auto x : Adj[node]) { if(x == p or Mark[x]) { continue; } if(2 * sz[x] > cursz) { return FindCen(x, node, cursz); } } return node; } vector <int> Cur; void Cal(int node, int p) { sz[node] = 1; for(auto x : Adj[node]) { if(x == p or Mark[x]) { continue; } H[x] = H[node] + 1; Cal(x, node); sz[node] += sz[x]; } if(Cur.empty() or Cur[0] < sz[node]) { // do nothing } else { int id = upper_bound(Cur.begin(), Cur.end(), sz[node], greater <int> ()) - Cur.begin() - 1; assert(id >= 0); ans[2 * sz[node]] = max(ans[2 * sz[node]], H[node] + id + 3); } nw[H[node]] = max(nw[H[node]], sz[node]); } void Cal2(int node, int p, int s) { for(auto x : Adj[node]) { if(x == p or Mark[x]) { continue; } Cal2(x, node, s); } if(Cur.empty() or Cur[0] < sz[node]) { // do nothing } else { int id = upper_bound(Cur.begin(), Cur.end(), sz[node], greater <int> ()) - Cur.begin() - 1; assert(id >= 0); ans[2 * sz[node]] = max(ans[2 * sz[node]], H[node] + id + 3); } nw[H[node]] = max(nw[H[node]], sz[node]); ans[2 * min(s, sz[node])] = max(ans[2 * min(s, sz[node])], H[node] + 2); } void Solve(int node, int p) { DFS(node, p); int cen = FindCen(node, p, sz[node]); Mark[cen] = true; Cur.clear(); int ss = sz[node]; for(auto x : Adj[cen]) { H[x] = 0; if(Mark[x]) { continue; } Cal(x, cen); for(int i = 0; ; i++) { if(nw[i] == 0) { break; } if(i < (int)Cur.size()) { Cur[i] = max(Cur[i], nw[i]); } else { Cur.push_back(nw[i]); } nw[i] = 0; } } Cur.clear(); reverse(Adj[cen].begin(), Adj[cen].end()); for(auto x : Adj[cen]) { H[x] = 0; if(Mark[x]) { continue; } Cal2(x, cen, ss - sz[x]); for(int i = 0; ; i++) { if(nw[i] == 0) { break; } if(i < (int)Cur.size()) { Cur[i] = max(Cur[i], nw[i]); } else { Cur.push_back(nw[i]); } nw[i] = 0; } } for(auto x : Adj[cen]) { if(!Mark[x]) { Solve(x, cen); } } } int main() { // freopen("Input.txt", "r", stdin); // freopen("Output2.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; Adj[u].push_back(v); Adj[v].push_back(u); } Solve(1, -1); for(int i = n; i >= 1; i--) { ans[i] = max(ans[i], ans[i + 1]); } for(int i = 1; i <= n; i++) { if(i & 1) { cout << 1 << '\n'; } else { cout << max(ans[i], 1) << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...