제출 #1011639

#제출 시각아이디문제언어결과실행 시간메모리
1011639biximoMeetings 2 (JOI21_meetings2)C++17
0 / 100
1 ms8540 KiB
#include <bits/stdc++.h> #define N 200005 #define INF 1000000000 using namespace std; int n, sz[N], dpt[N], tb[N][18]; vector<int> adj[N]; bool vs[N]; void size_DFS(int c, int p) { sz[c] = 1; for(int i = 1; i < 18; i ++) { tb[c][i] = tb[tb[c][i-1]][i-1]; } for(int i: adj[c]) { if(i == p) continue; dpt[i] = dpt[c]+1; tb[i][0] = c; size_DFS(i, c); sz[c] += sz[i]; } } int jump(int a, int ds) { for(int i = 0; i < 18; i ++) { if(ds&1<<i) a = tb[a][i]; } return a; } int LCA(int a, int b) { if(dpt[a] != dpt[b]) { if(dpt[a] < dpt[b]) swap(a,b); a = jump(a, dpt[a]-dpt[b]); } if(a == b) return a; for(int i = 17; i >= 0; i --) { if(tb[a][i] != tb[b][i]) { a = tb[a][i]; b = tb[b][i]; } } return tb[a][0]; } int getSize(int c, int rt) { int lca = LCA(c,rt); if(lca != c) { return sz[c]; } else { assert(dpt[rt] > dpt[c]); return sz[1]-sz[jump(rt,dpt[rt]-dpt[c]-1)]; } } int sub_sz[N]; void size_2_DFS(int c, int p) { sub_sz[c] = 1; for(int i: adj[c]) { if(vs[i] || i == p) continue; size_2_DFS(i, c); sub_sz[c] += sub_sz[i]; } } int find_cent_DFS(int c, int p, int tree_sz) { for(int i: adj[c]) { if(i == p || vs[i] || sub_sz[i]*2<tree_sz) continue; return find_cent_DFS(i, c, tree_sz); } return c; } struct Segtree { vector<int> tree; int len; void init(int n) { len = 1; while(len < n) len *= 2; tree = vector<int>(len*2,-INF); } void update(int a, int v) { tree[a+len] = max(tree[a+len],v); for(a = (a+len)>>1; a >= 1; a >>= 1) { tree[a] = max(tree[a*2],tree[a*2+1]); } } void erase(int a) { tree[a+len] = -INF; for(a = (a+len)>>1; a >= 1; a >>= 1) { tree[a] = max(tree[a*2],tree[a*2+1]); } } int query(int a, int b) { int res = -INF; for(a += len, b += len; a <= b; a >>= 1, b >>= 1) { if(a&1) res = max(res, tree[a++]); if(~b&1) res = max(res, tree[b--]); } return res; } Segtree() {} } tree; int ans[N]; void ans_DFS(int c, int dt, int p, int rt) { for(int i: adj[c]) { if(vs[i] || i == p) continue; ans_DFS(i, dt+1, c, rt); } if(c == rt) return; int csz = getSize(c, rt); ans[csz] = max(ans[csz], dt+tree.query(csz,tree.len-1)+1); int rsz = getSize(rt, c); ans[min(rsz,csz)] = max(ans[min(rsz,csz)], dt+1); } void upd_DFS(int c, int dt, int p, int rt) { for(int i: adj[c]) { if(vs[i] || i == p) continue; upd_DFS(i, dt+1, c, rt); } if(c == rt) return; int csz = getSize(c, rt); tree.update(csz, dt); } void ers_DFS(int c, int dt, int p, int rt) { for(int i: adj[c]) { if(vs[i] || i == p) continue; ers_DFS(i, dt+1, c, rt); } if(c == rt) return; int csz = getSize(c, rt); tree.erase(csz); } void centroid_DFS(int c) { size_2_DFS(c, -1); int cent = find_cent_DFS(c, -1, sub_sz[c]); vs[cent] = 1; for(int i: adj[cent]) { if(vs[i]) continue; ans_DFS(i, 1, cent, cent); upd_DFS(i, 1, cent, cent); } for(int i: adj[cent]) { ers_DFS(i, 1, cent, cent); } for(int i: adj[cent]) { if(vs[i]) continue; centroid_DFS(i); } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; tree.init(n); for(int i = 1, u, v; i < n; i ++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } size_DFS(1,-1); centroid_DFS(1); for(int i = n/2; i >= 1; i --) { ans[i] = max(ans[i], ans[i+1]); } for(int i = 1; i <= n; i ++) { if(i%2) cout << "1\n"; else cout << ans[i/2] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...