Submission #991216

#TimeUsernameProblemLanguageResultExecution timeMemory
99121612345678Meetings 2 (JOI21_meetings2)C++17
0 / 100
13 ms24152 KiB
#include <bits/stdc++.h> using namespace std; const int nx=2e5+5, kx=20; int n, u, v, sz[nx], dist[nx][kx], c[nx], lvl[nx], used[nx], vs[nx], pa[nx][kx], res[nx], mx, ans[2*nx], lvl2[nx], in[nx], out[nx], t; vector<int> d[nx], upd, szz[nx], rsz[nx]; multiset<pair<int, int>> ms[nx]; priority_queue<pair<int, int>> pq; int dfssz(int u, int p) { sz[u]=1; for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u); return sz[u]; } int findcentroid(int u, int p, int rtsz) { for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz); return u; } void filldist(int u, int p, int w, int l) { dist[u][l]=w; for (auto v:d[u]) if (v!=p&&!used[v]) filldist(v, u, w+1, l); } void decomposition(int u, int p) { u=findcentroid(u, u, dfssz(u, u)); used[u]=1; lvl[u]=(p!=-1)?(lvl[p]+1):0; c[u]=p; filldist(u, u, 0, lvl[u]); for (auto v:d[u]) if (v!=p&&!used[v]) decomposition(v, u); } void dfs(int u, int p) { in[u]=++t; pa[u][0]=p; lvl2[u]=lvl2[p]+1; for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1]; sz[u]=1; for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v]; out[u]=t; } int query(int u) { int mxd=0, st=u; while (c[u]!=-1) { if (!ms[c[u]].empty()&&prev(ms[c[u]].end())->second!=u) mxd=max(mxd, dist[st][lvl[c[u]]]+prev(ms[c[u]].end())->first); else if (ms[c[u]].size()>=2) mxd=max(mxd, dist[st][lvl[c[u]]]+prev(prev(ms[c[u]].end()))->first); u=c[u]; } return mxd; } void open(int u) { int st=u; while (c[u]!=-1) ms[c[u]].insert({dist[st][lvl[c[u]]], u}), u=c[u]; } void close(int u) { int st=u; while (c[u]!=-1) ms[c[u]].erase(ms[c[u]].find({dist[st][lvl[c[u]]], u})), u=c[u]; } struct segtree { int d[4*nx]; void update(int l, int r, int i, int idx, int vl) { if (r<idx||idx<l) return; if (l==r) return d[i]=vl, void(); int md=(l+r)/2; update(l, md, 2*i, idx, vl); update(md+1, r, 2*i+1, idx, vl); d[i]=max(d[2*i], d[2*i+1]); } int query(int l, int r, int i, int ql, int qr) { if (qr<l||r<ql) return 0; if (ql<=l&&r<=qr) return d[i]; int md=(l+r)/2; return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr)); } } s; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n; for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u); decomposition(1, -1); //for (int i=1; i<=n; i++) cout<<"centroid "<<i<<' '<<c[i]<<'\n'; dfs(1, 1); pq.push({sz[1], 1}); while (!pq.empty()) { auto [w, u]=pq.top(); pq.pop(); open(u); if (pa[u][0]!=u&&!vs[pa[u][0]]) close(pa[u][0]), vs[pa[u][0]]=1; res[w]=max(res[w], query(u)); for (auto v:d[u]) if (v!=pa[u][0]) pq.push({sz[v], v}); } for (int i=1; i<=n; i++) { if (sz[1]-sz[i]<sz[i]) continue; int u=i; for (int j=kx-1; j>=0; j--) if (sz[1]-sz[pa[u][j]]>=sz[i]) u=pa[u][j]; res[sz[i]]=max(res[sz[i]], lvl2[i]-lvl2[u]+1); } for (int i=1; i<=n; i++) szz[sz[i]].push_back(i), rsz[sz[1]-sz[i]].push_back(i); for (int i=n; i>=1; i--) { for (auto u:szz[i]) s.update(1, n, 1, in[u], lvl2[u]); for (auto u:rsz[i]) res[i]=max(res[i], s.query(1, n, 1, in[u], out[u])-lvl2[u]+1); } for (int i=n; i>=1; i--) res[i]=max(res[i], res[i+1]); for (int i=1; i<=n; i++) ans[i]=1; for (int i=1; i<=n; i++) ans[2*i]=max(ans[2*i], res[i]+1); for (int i=1; i<=n; i++) cout<<ans[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...