数据生成器：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
mt19937 rnd(time(nullptr));
int main(){
    ios::sync_with_stdio(0);
    freopen("price17.in","w",stdout);
    cout<<N<<" "<<1<<" "<<N<<"\n";
    for(int i=1;i<=N;i++){
        if(rnd()%40000==0) cout<<"1";
        else cout<<"0";
    }
    cout<<"\n";
    for(int i=2;i<=N;i++){
        if(i%50000<=114) cout<<1<<" "<<i<<"\n";
        else cout<<i-1<<" "<<i<<"\n";
    }
    return 0;
}

P9132

考虑如何对一个给定的 \(T\) 求值。不妨设为 \(s_T\) 。

我们设 \(dp_{u,1}\) 为连通块包含 \(u\) 时的最小代价，\(dp_{u,0}\) 为不包含 \(u\) 的最小代价。显然列出转移方程：

\(dp_{u,0}=\sum _\limits{v\in S_u} \min(dp_{u,0},dp_{u,1}+T)\)。

\(dp_{u,1}=\sum _\limits{v\in S_u} \min(dp_{u,0},dp_{u,1})\) 。

初值为 \(dp_{u,1}=1,dp_{u,0}=\operatorname{inf}t_u\) 。

对于每个 \(T\) 做 dp 可以做到 \(O(n^2)\) 。注意到，\(T\) 很大时联通块个数很少。具体的，\(Tw_T \le n+T\) ，故 \(T\ge \sqrt{n}\) 时 \(w_T\le O(\sqrt n)\)。

因此，\(T\ge \sqrt n\) 时，\(s_{T+1}-s_T\) 至多有 \(O(\sqrt n)\) 次改变。可以直接二分改变的位置，做到 \(O(\dfrac{n}{B} \log n+Bn)\) ，取 \(B=\sqrt{n \log n}\) 时最优。

实现时，可以记录 \(dfn\) 序后从儿子向父亲计算贡献而不用进行 dfs 。实际上，取 \(B=\sqrt n\) 会比 \(B=\sqrt{n \log n}\) 更快。

std

#include<iostream>
#include<cmath>
using namespace std;
const int N=2e5+5;
struct edge{
    int v,nxt;
};
edge e[N*2];
int h[N],tot;
int n,L,R,k,v[N],f[N];
int dfn[N],c,ans[N];
int pt[N];
int dp[N][2];
void add(int u,int v){
    e[++tot].v=v;
    e[tot].nxt=h[u];
    h[u]=tot;
}
void dfs(int u){
    dfn[++c]=u;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==f[u]) continue;
        f[v]=u;
        dfs(v);
    }
}
int solve(int k){
    if(pt[k]) return pt[k];
    for(int i=1;i<=n;i++){
        if(v[i]) dp[i][0]=1e9;
        else dp[i][0]=0;
        dp[i][1]=1;
    }
    for(int I=n;I;I--){
        int i=dfn[I];
        int u=f[i];
        dp[u][0]+=min(dp[i][0],dp[i][1]+k);
        dp[u][1]+=min(dp[i][0],dp[i][1]);
    }
    return pt[k]=min(dp[1][0],dp[1][1]+k);
}
int main(){
    freopen("price.in","r",stdin);
    freopen("price.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n>>L>>R;
    for(int i=1;i<=n;i++){
        char ch;
        cin>>ch;
        v[i]=ch-'0';
    }
    for(int i=1,a,b;i<n;i++){
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    k=sqrt(n);
    for(int i=1;i<=k;i++) ans[i]=solve(i);
    int l=k+1,pre=solve(k+1)-solve(k);
    while(l<=n){
        int L=l,R=n+1,lst;
        while(L<R){
            int mid=(L+R)>>1,d=solve(mid)-solve(mid-1);
            if(d==pre) L=mid+1;
            else{
                R=mid;
                lst=d;
            }
        }
        int x=solve(l);
        for(int i=l;i<L;i++) ans[i]=x+pre*(i-l);
        l=L;
        pre=lst;
    }
    for(int i=L;i<=R;i++) cout<<ans[i]<<"\n";
    return 0;
}