题解归档 - cf2220E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2220E
• 本地来源：problems/cf2220E/idea.md
• 题目链接：https://codeforces.com/contest/2220/problem/E
• 原始标题：cf2220E 思路记录

思路

cf2220E 思路记录

v4 — 外部题解 paste（模板 Agent 测试用）

• B 连通块；DP 树上 R 为叶子。
• dp[u][0/1]：u 比父亲先/后染红。
• R 叶子 0,inf；B 叶子 inf,1。
• 儿子按 dp1-dp0 排序，前缀转移（dp0 非空前缀，dp1 可空）。
• 实现：每 B 块对每个根 DFS（儿子含 R），块贡献 min_r min(dp0,dp1) 累加。

模板来源

• lib/动态规划(树型dp).cpp → ss[] + DFS
• agent/TEMPLATE_GEN.md / template_sources.json

验证

• [x] 官方样例 3 组：1.0 / 4.5 / 2.0
• [x] watest.in：4.5
• [ ] fail.in：sol 5.333 vs brute 5.0（块间/选根待讨论）
• [ ] 全随机 stress 仍有 inf 个例（需和你多轮对齐题解细节）

历史

• v1 BFS 逐点 (d/r) 相加 → WA
• v2 固定 (r/\deg) 贪心策略 → 部分 WA
• v3 B 块分解（未写完）

代码

来源：problems/cf2220E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:40:56
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
const double inf=1e100;
vector<ll>ss[maxn],ch,comp;
ll col[maxn],vis[maxn];
double dp0[maxn],dp1[maxn];
queue<ll>q;
string st;
struct zc{
    double d,c0,c1;
    ll id;
};
vector<zc>ord;
void dfs(ll u,ll p){
    ll i,v;
    ch.clear();
    for(i=0;i<(ll)ss[u].size();i++){
        v=ss[u][i];
        if(v==p) continue;
        ch.push_back(v);
    }
    if(col[u]){
        dp0[u]=0;
        dp1[u]=inf;
        return;
    }
    if(ch.empty()){
        dp0[u]=inf;
        dp1[u]=1;
        return;
    }
    for(i=0;i<(ll)ch.size();i++) dfs(ch[i],u);
    ord.clear();
    for(i=0;i<(ll)ch.size();i++){
        zc z;
        v=ch[i];
        z.id=v;
        z.c0=dp0[v];
        z.c1=dp1[v];
        z.d=z.c1-z.c0;
        ord.push_back(z);
    }
    sort(ord.begin(),ord.end(),[](zc a,zc b){
        if(fabs(a.d-b.d)>1e-12) return a.d<b.d;
        return a.id<b.id;
    });
    ll m=ord.size(),k;
    dp0[u]=inf;
    for(k=1;k<=m;k++){
        double cur=(m+1.0)/k;
        for(i=0;i<k;i++) cur+=ord[i].c0;
        for(i=k;i<m;i++) cur+=ord[i].c1;
        dp0[u]=min(dp0[u],cur);
    }
    dp1[u]=inf;
    for(k=0;k<=m;k++){
        double cur=(m+1.0)/(k+1);
        for(i=0;i<k;i++) cur+=ord[i].c0;
        for(i=k;i<m;i++) cur+=ord[i].c1;
        dp1[u]=min(dp1[u],cur);
    }
}
int main(){
    ll t,n,i,j,k,u,v,r,x;
    double ans,best;
    cin>>t;
    while(t--){
        cin>>n>>st;
        for(i=1;i<=n;i++){
            ss[i].clear();
            col[i]=st[i-1]-'0';
            vis[i]=0;
        }
        for(i=1;i<n;i++){
            cin>>j>>k;
            ss[j].push_back(k);
            ss[k].push_back(j);
        }
        ans=0;
        for(i=1;i<=n;i++){
            if(col[i] or vis[i]) continue;
            comp.clear();
            while(!q.empty()) q.pop();
            q.push(i);
            vis[i]=1;
            while(!q.empty()){
                u=q.front();
                q.pop();
                comp.push_back(u);
                for(j=0;j<(ll)ss[u].size();j++){
                    v=ss[u][j];
                    if(!col[v] and !vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
            best=inf;
            for(j=0;j<(ll)comp.size();j++){
                r=comp[j];
                for(k=0;k<(ll)comp.size();k++){
                    x=comp[k];
                    dp0[x]=dp1[x]=0;
                }
                dfs(r,0);
                best=min(best,min(dp0[r],dp1[r]));
            }
            ans+=best;
        }
        cout<<fixed<<setprecision(10)<<ans<<"\n";
    }
    return 0;
}