采用了更加好想的根号分治做法。
首先需要会对单独的常数 \(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;
}