[??记录]CF1039D You Are Given a Tree
command_block
·
·
个人记录
题意 ： 给出一棵 n 个节点的树。
对于 k=1...n ，分别求出最大的点不相交的长为 k 的简单路径集合大小。
------------
咱也没刻意挑题啊，咋个个都是根号题目啊……
首先思考如何对指定的 $k$ 求解。可以考虑贪心。
从低到高考虑，若能在子树内合成一条链则尽量合成。
具体实现 ： 维护子树内还能向下延伸的最长链长度 $f[u]$。
将儿子中 $f$ 的最大值和次大值合并，若可以拼成符合要求的链，则拼接，并将 $f$ 置为 $0$，否则继承儿子的最大值。
设一个阈值 $B$。
对于 $k\leq B$ 的部分，暴力重复求解，复杂度为 $O(nB)$。
对于 $k>B$ 的部分，显然答案 $< n/B$，而答案又是单调不增的，所以分为了 $O(n/B)$ 个段。
可以二分出每个段的具体位置，复杂度为 $O(n^2\log n/B)$。
综上，令 $B=\sqrt{n\log n}$ 即可得到复杂度为 $O(n\sqrt{n\log n})$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define MaxN 100500
using namespace std;
vector<int> g[MaxN];
int p[MaxN],f[MaxN],tn;
void pfs(int u,int fa)
{
f[u]=fa;
for (int i=0;i<g[u].size();i++)
if (g[u][i]!=fa)
pfs(g[u][i],u);
p[++tn]=u;
}
int n,mx[MaxN];
int calc(int lim)
{
int cnt=0;
for (int t=1;t<=n;t++){
int u=p[t],l0=0,l1=0;
for (int i=0;i<g[u].size();i++)
if (f[u]!=g[u][i]){
int sav=mx[g[u][i]];
if (sav>l0){l1=l0;l0=sav;}
else l1=max(l1,sav);
}
if (l0+l1+1>=lim){cnt++;mx[u]=0;}
else mx[u]=l0+1;
}return cnt;
}
int nxt(int l,int c)
{
int r=n,mid;
while(l<r){
mid=(l+r+1)>>1;
if (calc(mid)==c)l=mid;
else r=mid-1;
}return l;
}
int BS;
int main()
{
scanf("%d",&n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}pfs(1,0);
BS=min((int)sqrt(n*log(n)),n);
for (int i=1;i<=BS;i++)
printf("%d ",calc(i));
for (int i=BS+1;i<=n;){
int sav=calc(i),p=nxt(i,sav);
for (int j=i;j<=p;j++)
printf("%d ",sav);
i=p+1;
}return 0;
}
```