P9132 [USACO23FEB] Watching Cowflix P 题解

采用了更加好想的根号分治做法。

首先需要会对单独的常数 \(k\) 树形 DP 计算。树上连通块问题，考虑在最浅的节点统计贡献，因为这样的点只有一个，最方便统计贡献。于是设 \(f_{u,0/1}\) 表示考虑到节点 \(u\)，节点 \(u\) 在/不在一个连通块中的贡献。转移有

\[\begin{cases} \displaystyle f_{u,0}=\sum_{v\in\text{son}(u)}\min(f_{v,0},f_{v,1}+k)\\ \displaystyle f_{u,1}=1+\sum_{v\in\text{son}(u)}\min(f_{v,0},f_{v,1}) \end{cases} \]

注意当 \(s_u=\tt1\) 时，\(f_{u,0}\) 的状态是不合法的，需要设为极大值以排除。最后答案是 \(\min(f_{1,0},f_{1,1}+k)\)。

然后考虑根号分治，实际上这题的根号分治还是有点注意力的。首先答案显然单增，但额外需要注意到的一点是答案的差值单调不增。原因是 \(k\) 固定时答案可以看作若干个关于 \(k\) 的一次函数的最小值，这显然是下凸的，所以有差值不增的性质。

并且这个差值减小的速度也是递减的。也就是说取一个阈值 \(B\)，当 \(k\le B\) 时差值递减地很快，但当 \(k>B\) 时差值递减的速度就变慢了。于是考虑对 \(k\le B\) 每次 \(O(n)\) 树形 DP 暴力求解，对于 \(k>B\) 时二分找到差值不同的位置，那么中间这一段的答案就可以由一个固定的差值递推求解。因此总的复杂度是 \(O(nB+dn\log n)\) 的，其中 \(d\) 是 \(k=B+1\) 和 \(k=B\) 时答案的差值。

然后这个 \(B\) 取一个 \(\sqrt n\) 就过了。

#include<bits/stdc++.h>
#define il inline
using namespace std;

constexpr int MAXN=2e5+5;
int n,head[MAXN],tot;
string s;
struct{
	int v,to;
}e[MAXN<<1];
il void addedge(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
namespace K{
	int g[MAXN][2],K;
	int ans[MAXN];
	il void dfs(int u,int fno){
		g[u][0]=0,g[u][1]=1;
		for(int i=head[u],v;i;i=e[i].to){
			if((v=e[i].v)==fno) continue;
			dfs(v,u);
			g[u][0]+=min(g[v][0],g[v][1]+K);
			g[u][1]+=min(g[v][0],g[v][1]);
		}
		if(s[u]=='1') g[u][0]=0x3f3f3f3f;
	}
	il int gt(int k){
		if(k>n) return 0;
		if(ans[k]) return ans[k];
		K=k;
		dfs(1,0);
		return ans[k]=min(g[1][0],g[1][1]+k);
	}
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n>>s,s=' '+s;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		addedge(u,v),addedge(v,u);
	}
	int B=sqrt(n);
	for(int k=1;k<=B;k++) cout<<K::gt(k)<<'\n';
	int dt=K::gt(B+1)-K::gt(B);
	cout<<K::gt(B+1)<<'\n';
	for(int ndt=dt,pos=B+1;ndt>0;){
		int l=pos+1,r=n,ans=pos;
		while(l<=r){
			int mid=(l+r)>>1;
			if(K::gt(mid)-K::gt(mid-1)==ndt) ans=mid,l=mid+1;
			else r=mid-1;
		}
		int lst=K::gt(pos);
		for(int j=1;j<=ans-pos;j++) cout<<(lst+=ndt)<<'\n';
		pos=ans+1;
		if(pos>n) break;
		ndt=K::gt(pos)-K::gt(ans);
		cout<<K::gt(pos)<<'\n';
	}
	return 0;
}