Submission #971265

#	Time	Username	Problem	Language	Result	Execution time	Memory
971265		huutuan	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	5 ms	27292 KiB

meetings2

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10, LG=18;
int n, sz[N], ans[N], dep[N], up[LG][N], tin[N], tout[N], tdfs, par[N];
vector<int> g[N], vv[N];

void dfs(int u, int p){
   tin[u]=++tdfs;
   dep[u]=dep[p]+1;
   for (int k=1; k<LG; ++k) up[k][u]=up[k-1][up[k-1][u]];
   for (int v:g[u]) if (v!=p){
      up[0][v]=u;
      dfs(v, u);
   }
   tout[u]=tdfs;
}

int lca(int u, int v){
   if (dep[u]!=dep[v]){
      if (dep[u]<dep[v]) swap(u, v);
      int d=dep[u]-dep[v];
      for (int k=0; k<LG; ++k) if (d>>k&1) u=up[k][u];
   }
   if (u==v) return u;
   for (int k=LG-1; k>=0; --k) if (up[k][u]!=up[k][v]) u=up[k][u], v=up[k][v];
   return up[0][u];
}

int distance(int u, int v){
   return dep[u]+dep[v]-dep[lca(u, v)]*2;
}

void dfs_sz(int u, int p){
   sz[u]=1;
   par[u]=p;
   for (int v:g[u]) if (v!=p){
      dfs_sz(v, u);
      sz[u]+=sz[v];
   }
}

int find_centroid(int u, int p){
   for (int v:g[u]) if (v!=p && sz[v]*2>n) return find_centroid(v, u);
   return u;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<n; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i=1; i<=n; i+=2) ans[i]=1;
   dfs(1, 0);
   dfs_sz(1, 0);
   int cen=find_centroid(1, 0);
   dfs_sz(cen, 0);
   for (int i=1; i<=n; ++i) if (i!=cen) vv[sz[i]].push_back(i);
   set<int> st;
   pair<int, int> p={-1, -1};
   auto insert=[&](int u){
      st.insert(u);
      st.erase(par[u]);
      if ((int)st.size()==1) p={-1, -1};
      else if ((int)st.size()==2) p={*st.begin(), *st.rbegin()};
      else{
         if (p.first==par[u]) p.first=u;
         else if (p.second==par[u]) p.second=u;
         else if (distance(u, p.second)>distance(p.first, p.second)) p.first=u;
         else if (distance(u, p.first)>distance(p.first, p.second)) p.second=u;
      }
   };
   for (int i=n-(n&1); i>=2; i-=2){
      for (auto &j:vv[i/2]) insert(j);
      ans[i]=(p.first==-1)?1:distance(p.first, p.second)+1;
   }
   int mxsz=0;
   for (int u:g[cen]) mxsz=max(mxsz, sz[u]);
   for (int i=n-(n&1); i>=2; i-=2) if (mxsz>=i/2) ans[i]=max(ans[i], 2);
   for (int i=1; i<=n; ++i) cout << ans[i] << '\n';
   return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80