传送门
题意简述
给出 (1) 棵(n)个节点的树，对于 ([l,r]) 间的每 (1) 个数 (k)，你需要求出：最多能选出多少条互不相交的路径，每条路径的长度都为 (k)？
解析
一开始假设 (k) 是确定的，我们可以考虑暴力。不妨设 (f_x) 为以 (x) 为根中最长链的长度。转移方式就是能合并就合并，反之选一条最长的链向上延伸，每一次时间复杂度为 (O(n))。
通过玄学的计算我们可以发现 (klesqrt{n}) 的时候答案最多只有 (sqrt{n}) 种取值，(k>sqrt{n}) 也一样。并且答案大小的具有单调性（这十分显然，链越长答案越少）。于是我们直接二分边界，统计答案即可，复杂度为(O(nsqrt{n}log_2n))。
我这里用的是别的方法整体二分，复杂度一样（好写一些）。
Code：
#include<bits/stdc++.h>
namespace mystd {
using namespace std;
#define LL long long
inline LL read() {
char c=getchar();
LL sum=0;
while(c<'0'||c>'9') {
c=getchar();
}
while(c>='0'&&c<='9') {
sum=(sum<<3)-'0'+(sum<<1)+c,c=getchar();
}
return sum;
}
inline void write(LL x) {
if(x>9) {
write(x/10);
}
putchar(x%10+'0');
}
const int d[4][2]= {
{1,0},{0,1},{-1,0},{0,-1}
},mod=998244353,N=1e5+5;
}
using namespace Bu_Yao_Tian_Tian_Bi_Sai;
struct edge {
int to,nxt;
} e[N<<1];
int cnt,head[N];
void add(int u,int v) {
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int n=read(),ans[N],f[N];
void dp(int u,int fa,int len) {
f[u]=0;
int maxn=0,sec=0;
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(v==fa) {
continue ;
}
dp(v,u,len);
if(f[v]>=maxn) {
sec=maxn,maxn=f[v];
} else {
sec=max(sec,f[v]);
}
}
if(sec+maxn+1>=len) {
cnt++;
} else {
f[u]=maxn+1;
}
}
void fen(int st,int nd,int l,int r) {
if(st>nd||l>r) {
return ;
}
if(l==r) {
for(int i=st; i<=nd; i++) {
ans[i]=l;
}
return ;
}
int mid=(st+nd)>>1;
cnt=0;
dp(1,0,mid);
ans[mid]=cnt;
fen(st,mid-1,cnt,r),fen(mid+1,nd,l,cnt);
}
int main() {
for(int i=1,u,v; i<n; i++) {
u=read(),v=read(),add(u,v),add(v,u);
}
fen(1,n,0,n);
for(int i=1; i<=n; i++) {
write(ans[i]),putchar(' ');
}
return 0;
}
完美撒花~
