正題

題目鏈接:https://www.luogu.com.cn/problem/CF1039D

---

題目大意

給出$n$個(gè)點(diǎn)的一棵樹，然后對于$k\in [1,n]$求每次使用一條長度為$k$的鏈覆蓋樹并且不能重復(fù)覆蓋點(diǎn)時(shí)最大覆蓋條數(shù)。

$1\le n\le 10^5$

---

解題思路

先考慮暴力怎么做，因?yàn)槊織l鏈的價(jià)值都是一，顯然的一種貪心思想是能合并的就合并（沒有讓出一條鏈給另一條鏈騰空間的必要）。

這樣的復(fù)雜度是$O(n)$的，但是對于每個(gè)都要求所以需要優(yōu)化。

之后考慮上根號分治，對于一個(gè)$k$的答案顯然不會(huì)超過$\frac{n}{k}$，所以可以當(dāng)$k\le \sqrt{n}$的時(shí)候暴力做，然后由于答案遞增，大于$\sqrt{n}$的$k$答案的取值不會(huì)超過$\sqrt{n}$，每次二分?jǐn)帱c(diǎn)即可。時(shí)間復(fù)雜度$O(n\sqrt{n}\log n)$。

其實(shí)發(fā)現(xiàn)這樣還是不夠快，可以找到一個(gè)更好的閾值，設(shè)為$T$，那么前面的復(fù)雜度就是$T$，后面的復(fù)雜度就是$\frac{n}{T}\log n$，用平衡規(guī)劃的思想當(dāng)$T=\frac{n}{T}\log n$時(shí)最快，也就是$T=\sqrt{n\log n}$時(shí)最快了。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N<<1]; int n,tot,cnt,dfn[N],ls[N],fa[N],f[N]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){dfn[++cnt]=x;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x])continue;fa[y]=x;dfs(y);}return; } int solve(int k){if(k==1)return n;int ans=0;for(int i=1;i<=n;i++)f[i]=1;for(int i=n;i>=1;i--){int x=dfn[i];if(f[x]&&f[fa[x]]){if(f[x]+f[fa[x]]>=k)ans++,f[fa[x]]=0;else f[fa[x]]=max(f[fa[x]],f[x]+1);}}return ans; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs(1);int T=sqrt((double)n*(log(n)/log(2))),last,z=T+1;for(int i=1;i<=T;i++)printf("%d\n",last=solve(i));while(z<=n){int l=z+1,r=n,k=solve(z);while(l<=r){int mid=(l+r)>>1;if(solve(mid)<k)r=mid-1;else l=mid+1;}for(int i=z;i<=r;i++)printf("%d\n",k);z=r+1;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1039D-You Are Given a Tree【根号分治,贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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