T2 You Are Given a Tree (CF1039D)
苹果蓝17
·
·
个人记录
T2 You Are Given a Tree (CF1039D)
CF传送门
洛谷传送门
题意简述
有一棵 n 个节点的树
在树上选择一些长度为 k 的路径，使得这些路径覆盖的点互不重复
求对于 k (1 \leq k \leq n) ，最多能选择多少条路径
数据范围
1 \leq n \leq 10^5
1 \leq u \leq v \leq n
题解
思路
首先从特殊情况考虑
覆盖问题自然可以考虑贪心
一条链，必定可以找出一个点作为“根”（即 $dep$ 最小的那个点）
对于一个节点 $o$ ，想要覆盖它
如果有一根长度为 $k$ 的链以 $o$ 为根，那自然把它数进来最好
不然就会占用 $o$ 上面的节点，显然不优
（那如果这样的链有很多条呢？
可 $o$ 只能用一次啊！选哪种都是一样的）
所以对于一个o来说，记录转移它子树最长链与次长链的长度即可 $O(n)$ 解决
***
一个 $k$ 的情况搞定了，但 $n$ 个 $k$ 就要 $O(n^2)
7s都无济于事
所以不妨来观察一下答案
显然，ans \leq n/k
而且 ans 必然是单调不增的
对任意一个 a 来说，前 a 个 k ，答案种数不超过 a 种；后 (n-a) 个 k ，答案种数不会超过 n/a+1 种 （0 - n/a)
所以答案种数不会超过 a+n/a \geq 2 \times \sqrt n/a 种（当 a 取 \sqrt n 时）
对前 \sqrt n 个来说，暴力枚举即可，反正也没多少个
对后 n-\sqrt n 个来说，就是枚举断点
有多个断点？
$\Rightarrow$ 分治+二分
$O(nlogn \sqrt n)
做法
首先，dp部分
用 f[i] 表示包括 i节点在内的，子树下最长链长度
然后转移即可
如果找得到的话，注意 $f[i]=0$ ，因为此节点不可再用了
***
分治+二分部分
用 $l$ ， $r$ 表示查找的区间
用 $L$ ， $R$表示查找的值域
如果值域确定下来了表明这是个断点，更新答案
否则dp一遍 $mid$ 的答案，再去分治
更新答案的方向应该不用管，是分治嘛，无论哪个方向都会更新到的
**注意事项**
· 代码有点难以理解，慢慢想
· max值的更新方式好像这样是最正确也是最易于理解的
我原来写的不知为何错了
**AC代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,sum,flag;
int f[N],ans[N];
struct abc{
int to,nxt;
}e[2*N];
int head[N],cnt;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int o,int fa){
int max1=0,max2=0;
for(int i=head[o];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,o);
if(f[v]>max1) max2=max1,max1=f[v];
else if(f[v]>max2) max2=f[v];
//这两行是更新max值
}
if(max1+max2+1>=k) sum++,f[o]=0;//如果找得到
else f[o]=max1+1;//找不到就更新f[o]
}
void solve(int l,int r,int L,int R){
if(l>r || L>R) return;
if(L==R){
for(int i=l;i<=r;i++) ans[i]=L;
return;//记得啊
}
int mid=(l+r)>>1;
k=mid,sum=0;
dfs(1,0);
//跑一遍mid的答案
ans[mid]=sum;//别忘了更新ans[mid]（因为下面不会枚举到这个点了）
solve(l,mid-1,sum,R);
solve(mid+1,r,L,sum);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=sqrt(n);i++){
k=i;
sum=0;//sum为单次答案计数
dfs(1,0);
ans[i]=sum;
}
solve(sqrt(n)+1,n,0,sqrt(n));
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
```