CF2220E/CF2219C Coloring a Red Black Tree Solution

div1

div2

小店解析：A C D1 D2，依旧掉分。

# 题解

我们观察样例中期望的计算，发现可以考虑一种贪心：考虑按照节点 $i$ 对于答案所作出的贡献从大往小维护，每次将它统计后更新相邻节点的期望，设 $d_i$ 表示 $i$ 连出去的边的个数，$v_i$ 表示 $i$ 所连的点中有多少个值已被染色。

Code

如你所见，这样会 WA on test 5。

hack 是这个：

1
9
011100000
2 5
1 3
1 9
4 9
5 9
6 9
7 8
7 9

我们发现图中更新完 1 号点之后先更新 9 号点是更优的，但原算法会先更新 5 号点。

我们考虑重新排列这个排序方式，对于点 $x$ 和 $y$，如果 $x$ 要排在 $y$ 前面，会分为两种情况：

• $x$ 和 $y$ 不相邻

这种情况就是按照之前的贪心来，即：

$$\frac {d_x} {v_x} \le \frac {d_y} {v_y}$$

• $x$ 和 $y$ 相邻

我们发现 $x$ 和 $y$ 会互相影响，这里我们可以把式子列出来：

$$\frac {d_x} {v_x} + \frac {d_y} {v_y + 1} \le \frac {d_x} {v_x + 1} + \frac {d_y} {v_y} \\ \frac {d_x} {v_x} - \frac {d_x} {v_x + 1} \le \frac {d_y} {v_y} - \frac {d_y} {v_y + 1} \\ \frac {d_x} {v_x \times (v_x + 1)} \le \frac {d_y} {v_y \times (v_y + 1)}$$

式子出来了，按照最后一个式子来排序即可。

这样写需要判断两点之间是否连边，不好写。

但是我们发现如果都按 $\frac {d_x} {v_x \times (v_x + 1)} \le \frac {d_y} {v_y \times (v_y + 1)}$ 排序只会拉大 $x$ 和 $y$ 不相邻的情况的差值，不会影响总的排序结果。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,du[N],val[N];
bool a[N];
vector<ll> v[N];
set<pair<ld,ll>> st;
inline void solve () {
    n=read();
    string s;
    cin>>s;
    for (ll i=1;i<=n;i++) {
        a[i]=(s[i-1]=='1');
        du[i]=val[i]=0;
        v[i].clear();
    }
    for (ll i=1;i<n;i++) {
        ll ul=read(),vl=read();
        v[ul].push_back(vl);
        v[vl].push_back(ul);
        du[ul]++;
        du[vl]++;
        if (a[vl]) {
            val[ul]++;
        }
        if (a[ul]) {
            val[vl]++;
        }
    }
    for (ll i=1;i<=n;i++) {
        if (!a[i]) {
            st.insert({1.0*du[i]/(val[i]*(val[i]+1)),i});
        }
    }
    ld ans=0;
    while (!st.empty()) {
        auto [num,d]=(*st.begin());
        st.erase(st.begin());
        ans+=1.0*du[d]/val[d];
        a[d]=1;
        for (auto it : v[d]) {
            if (!a[it]) {
                st.erase(st.find({1.0*du[it]/(val[it]*(val[it]+1)),it}));
                val[it]++;
                st.insert({1.0*du[it]/(val[it]*(val[it]+1)),it});
            }
        }
    }
    printf("%.7lf\n",ans);
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    T=read();
    while (T--) {
        solve();
    }
    return 0;
}
/**/