cf1039D

鏈接

cf

思路

一次k可以貪心O(n)算。
對(duì)于\(≤\sqrt{n}\)的k，暴力算。
對(duì)于\(＞\sqrt{n}\)的k，最多會(huì)有\(\sqrt{n}\)種答案，而且答案單調(diào)。
二分就行了。
復(fù)雜度\(O(nlogn+n\sqrt{n}logn)\)
遞歸會(huì)被卡，所以要記錄dfs序然后循環(huán)

代碼

#include <cstdio> #include <iostream> #include <cmath> using namespace std; const int _=1e5+7; inline int read() {int x=0,f=1;char s=getchar();for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';return x*f; } int n,g[_],head[_],tot,stak[_],fa[_],top; struct node {int v,nxt;}e[_<<1]; inline void add(int u,int v) {e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot;} void dfs(int u,int F) {fa[u]=F,stak[++top]=u;for(int i=head[u];i;i=e[i].nxt)if(e[i].v!=F) dfs(e[i].v,u); } int calc(int L) {int ans=0;for(int i=1;i<=n;++i) g[i]=1;for(int i=n;i>=2;--i) {int u=stak[i],v=fa[u];if (g[v]+g[u]>=L) ++ans,g[v]=0;else if(g[v]) g[v]=max(g[v],g[u]+1);}return ans; } int main() {n=read();for(int i=1,u,v;i<n;++i) {u=read(),v=read();add(u,v),add(v,u);}int k=sqrt(n*log2(n));printf("%d\n",n);dfs(1,0);for(int i=2;i<=k;++i) printf("%d\n",calc(i));for(int i=k+1;i<=n;) {int l=i,r=n,R=i,ans=calc(i);while(l<=r) {int mid=(l+r)>>1;if(calc(mid)==ans) R=mid,l=mid+1;else r=mid-1;}for(;i<=R;++i) printf("%d\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/dsrdsr/p/11405978.html

總結(jié)

以上是生活随笔為你收集整理的cf1039D 分块的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。