Submission #844818

#TimeUsernameProblemLanguageResultExecution timeMemory
844818CookieMeetings 2 (JOI21_meetings2)C++14
100 / 100
235 ms51108 KiB
#include<bits/stdc++.h> #define ll long long #define vt vector #define pb push_back #define pii pair<int, int> #define sz(v) (int)v.size() using namespace std; const ll base = 107, mod = 1e9 + 7; const int mxn = 2e5 + 5, inf = 1e9, sq = 400; int n; vt<int>adj[mxn + 1]; int dep[mxn + 1], up[mxn + 1][18], ans[mxn + 1], sz[mxn + 1]; int dfs_sz(int s, int pre){ sz[s] = 1; for(auto i: adj[s]){ if(i != pre){ sz[s] += dfs_sz(i, s); } } return(sz[s]); } pii centroid(int s, int pre, int need){ pii cand = make_pair(n, s); int mxsub = 0; for(auto i: adj[s]){ if(i != pre){ cand = min(cand, centroid(i, s, need)); mxsub = max(mxsub, sz[i]); } } mxsub = max(mxsub, need - sz[s]); cand = min(cand, make_pair(mxsub, s)); return(cand); } void dfs_lca(int s, int pre){ for(auto i: adj[s]){ if(i != pre){ dep[i] = dep[s] + 1; up[i][0] = s; dfs_lca(i, s); } } } int lca(int u, int v){ if(dep[u] < dep[v])swap(u, v); int k = dep[u] - dep[v]; for(int i = 0; i < 18; i++){ if(k & (1 << i)){ u = up[u][i]; } } if(u == v)return(u); //cout << u << " " << v << " "; for(int i = 17; i >= 0; i--){ if(up[u][i] != up[v][i]){ u = up[u][i]; v = up[v][i]; } } //cout << u << " " << v << " "; return(up[u][0]); } int dist(int u, int v){ return(dep[u] + dep[v] - 2 * dep[lca(u, v)]); } vt<int>events[mxn + 1]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } int c = centroid(1, -1, dfs_sz(1, -1)).second; dfs_sz(c, -1); dfs_lca(c, -1); for(int i = 1; i < 18; i++){ for(int j = 1; j <= n; j++){ up[j][i] = up[up[j][i - 1]][i - 1]; } } //cout << up[10][0]; int ld = c, rd = c, len = 0; for(int i = 1; i <= n; i++){ events[sz[i]].pb(i); } for(int i = n / 2; i >= 1; i--){ for(auto u: events[i]){ //sz[u] will always be the minimum :)) //cout << u << " "; int expand_rght = dist(ld, u), expand_lft = dist(u, rd); if(expand_rght > len){ len = expand_rght; rd = u; }else if(expand_lft > len){ len = expand_lft; ld = u; } } //cout << ld << " " << rd << " " << dist(ld, rd) << "\n"; ans[i] = len + 1; } for(int i = 1; i <= n; i++){ if(i & 1)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...