제출 #419475

#제출 시각아이디문제언어결과실행 시간메모리
419475amoo_safarMeetings 2 (JOI21_meetings2)C++17
100 / 100
536 ms49220 KiB
// vaziat meshki-ghermeze ! #include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; const int N = 2e5 + 10; const int Log = 20; vector<int> G[N]; vector< pair<int, int> > E[N]; int n; int sp[N][Log]; int sub[N], dep[N]; int DFS(int u, int p, int d){ sp[u][0] = p; sub[u] = 1; dep[u] = d; for(int l = 1; l < Log; l++) sp[u][l] = sp[ sp[u][l - 1] ][l - 1]; for(auto adj : G[u]) if(adj != p) sub[u] += DFS(adj, u, d + 1); E[min(n - sub[u], sub[u])].pb({u, p}); return sub[u]; } int LCA(int u, int v){ if(dep[u] < dep[v]) swap(u, v); for(int i = 0; i < Log; i++) if((dep[u] - dep[v]) >> i & 1) u = sp[u][i]; if(u == v) return u; for(int l = Log - 1; l >= 0; l--) if(sp[u][l] != sp[v][l]) u = sp[u][l], v = sp[v][l]; return sp[u][0]; } int dist(int u, int v){ return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; } int ans[N]; int mk[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; int u, v; for(int i = 1; i < n; i++){ cin >> u >> v; G[u].pb(v); G[v].pb(u); } DFS(1, 0, 0); u = -1, v = -1; for(int i = n; i >= 1; i--){ if(i & 1){ ans[i] = 1; continue; } for(auto [fr, to] : E[i / 2]){ if(u == -1) u = fr, v = to, mk[fr] = 1, mk[to] = 1; if(!mk[fr]){ if(dist(u, v) < dist(u, fr)) v = fr; if(dist(u, v) < dist(v, fr)) u = fr; mk[fr] = 1; } if(!mk[to]){ if(dist(u, v) < dist(u, to)) v = to; if(dist(u, v) < dist(v, to)) u = to; mk[to] = 1; } } ans[i] = u == -1 ? 1 : dist(u, v) + 1; } for(int i = 1; i <= n; i++) cout << ans[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...