제출 #1014738

#제출 시각아이디문제언어결과실행 시간메모리
1014738NintsiChkhaidzeMeetings 2 (JOI21_meetings2)C++17
0 / 100
3 ms5464 KiB
#include <bits/stdc++.h> #define pb push_back #define s second #define f first #define pb push_back #define pii pair <int,int> #define ll long long using namespace std; const int N = 2e5 + 5; vector <int> v[N]; int c = -1,ans[N],sz[N],dep[N],d[25][N]; pii arr[N]; int findcentroid(int x,int par,int n){ int s = 1; for (int to: v[x]){ if (to == par) continue; s += findcentroid(to,x,n); } if (c == -1 && (par == -1 || s * 2 >= n)) c = x; return s; } int lca(int x,int y){ if (dep[x] < dep[y]) swap(x,y); for (int i = 20; i >= 0; i--) if (dep[d[i][x]] >= dep[y]) x = d[i][x]; if (x == y) return x; for (int i = 20; i >= 0; i--) if (d[i][x] != d[i][y]) x = d[i][x],y = d[i][y]; return d[0][x]; } void dfs(int x,int par){ sz[x] = 1; d[0][x] = par; dep[x] = dep[par] + 1; for (int to: v[x]){ if (to == par) continue; dfs(to,x); sz[x] += sz[to]; } } int getdistance(int x,int y){ int c=lca(x,y); return dep[x]+dep[y]-2*dep[c]+1; } signed main() { ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int n; cin>>n; for (int i = 1; i < n; i++){ int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } findcentroid(1,-1,n); dfs(c,c); for (int j = 1; j <= 20 ; j++) for (int i = 1; i <= n; i++) d[j][i] = d[j - 1][d[j - 1][i]]; for (int i = 1; i <= n; i++) arr[i] = {sz[i],i}; sort(arr+1,arr+n+1); int d1 = 0,d2 = 0,D=0,mx = 0; for (int i = n; i >= 1; i--){ int x = arr[i].s; if (!d1) d1=d2=x,D=1; else{ if (getdistance(d1,x) > D) { d2 = x; D = getdistance(d1,x); } if (getdistance(d2,x) > D){ d1 = x; D = getdistance(d2,x); } } mx=max(mx,D); ans[arr[i].f] = mx; } for (int i = 1; i <= n; i++){ if (i&1) cout<<1<<endl; else cout<<ans[i/2]<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...