前言

完全没有思维难度的方法，但是无论从理论上还是实际上都能过。

场上秒了，但是被卡常了。。。

根号分治 $O(n^{\frac{3}{2}})$ 做法。

思路

拿到这种算代价的题第一步就是分析上界，显然，答案上界为 $n+k$。

上界与 $n$ 同阶，考虑当一个连通块代价为 $k$ 时，联通块的数量最多为 $\frac{n+k}{k+1}$ 个。

考虑根号分治，设 $B$，用 $O(nB)$ 的树形 dp 暴力枚举 $k$ 为 $[1,B]$ 时的代价，然后用 $O(\frac{n^2}{B})$ 的树形 dp 预处理连通块数量为 $[1,\frac{n}{B}]$ 时的代价。

平衡复杂度，算出 $B = \sqrt{n}$。

当然，由于会被卡空间，所以还是只能把块长开到 $120$ 左右。

upd：

感谢 @mazihang2022 的帮助，我纠正了该背包的复杂度不是 $O(n^{\frac{2}{3}})$ 而是 $O(n^{\frac{1}{2}})$。

同时，他也提供了一种卡树形背包空间的方法，详见 某期洛谷日报。可以用重链剖分优化空间至 $O(n \log n)$。

于是，该根号分治的最终复杂度是 $O(n \sqrt{n})$。

code

略微卡常，有两点优化。

1. 用 dfs 序预处理 dp 顺序。
2. 不用 vector 从父亲向儿子递推，而是记录父亲从儿子往父亲递推。

膜拜 @DeepSkyCore 帮我卡常！！！！111

#include<bits/stdc++.h>
using namespace std;
template<typename G> inline void read(G &x) {x=0;G f=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0'&&ch<='9') {x=x*10+(ch^48);ch=getchar();}x*=f;}
const int MAXN=2e5+5,MAXM=126;
int fa[MAXN];
vector<int> E[MAXN],G[MAXN];
int f[MAXN][MAXM][2],g[MAXN][2],siz[MAXN],dfn[MAXN],cnt;
bitset<MAXN> vis;
void bdfs(int u,int las) {
	dfn[++cnt]=u;
	for(auto v:E[u]) {
		if(v!=las) {
			fa[v]=u;
			G[u].emplace_back(v);
			bdfs(v,u);
		}
	}
}
void bfs(int u) {
	siz[u]=1;
	f[u][1][1]=1;
	if(!vis[u]) f[u][0][0]=0;
	for(auto v:G[u]) {
		bfs(v);
		siz[u]+=siz[v];
		for(int i=min(100,siz[u]);i>=0;--i) {
			int f0=1e9,f1=1e9;
			for(int j=0;j<=siz[v]&&j<=i;++j) {
				f0=min(f0,f[u][i-j][0]+min(f[v][j][0],f[v][j][1]));
				f1=min(f1,f[u][i-j][1]+min(f[v][j][0],min(f[v][j+1][1],f[v][j][1])));
			}
			f[u][i][0]=f0,f[u][i][1]=f1;
		}
	}
}
int n,u,v;
signed main() {
	memset(f,63,sizeof(f));
	read(n);
	for(int i=1;i<=n;++i) {
		char ch=getchar();
		while(ch!='0'&&ch!='1') ch=getchar();
		vis[i]=ch-'0';
	}
	for(int i=2;i<=n;++i) {
		read(u),read(v);
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	bdfs(1,0);
	for(int j=n;j>=1;--j){
		g[j][1]=2;
	}
	g[1][0]=(vis[1]?1e9:0);
	for(int i=1;i<=1.6e3&&i<=n;++i) {
		for(int j=n;j>=2;--j) {
			u=dfn[j];
			if(vis[u]) g[u][0]=1e9;
			g[fa[u]][0]+=min(g[u][0],g[u][1]);
			g[fa[u]][1]+=min(g[u][0],g[u][1]-i);
			g[u][0]=0,g[u][1]=i+2;
		}
		printf("%d\n",min(g[1][0],g[1][1]));
		g[1][0]=(vis[1]?1e9:0),g[1][1]=i+2;
	}
	bfs(1);
	for(int i=1.6e3+1;i<=n;++i) {
		int ans=1e9;
		for(int j=0;j<=125&&j<=n/i+1;++j) ans=min(ans,min(f[1][j][0],f[1][j][1])+j*i);
		printf("%d\n",ans);
	}
	return 0;
}