[CF2112E] Tree Colorings 题解

· · 题解

注意到赛事公告提醒了第三组数据的问题，即任意一对绿色点之间没有黄色和蓝色点。于是绿色点是一个连通块。

然后就有一个很明显的 dp，设 f_u 表示以 u 为根的子树方案数，这里令 u 为绿色。于是转移时每棵儿子的子树独立，并且额外有全涂蓝色或黄色两种情况，于是转移 f_u=\prod_{v\in\text{son}(u)}(f_v+2)。

然后对于原问题，尝试直接拼起来 dp，然后发现根节点比较恼人，因为不知道到底要分拆出来哪些东西。于是换一个思路，在一棵树的基础上再加上一个儿子，则有 f_u(f_v+2)\to f'_{u}，这样就有一个明显的递推。设 g_i 表示原问题 m=i 时的答案，则 g_{d}g_{\frac xd-2}\to g_x，其中 d\mid x。具体实现时钦定 d\ge \frac xd 然后分别执行 g_dg_{\frac xd-2}\to g_x,g_{d-2}g_{\frac xd}\to g_x 即可。

时间复杂度调和级数级。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=500007,ee=1e18;
ll n,f[maxn],cnt;
int main(void){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    memset(f,0x3f,sizeof(f));
    f[1]=1;
    for(ll d=1;d<maxn;d++){
        for(ll x=d,i=1;x<maxn&&i<=d;x+=d,i++){
            if(i>=3) f[x]=min(f[x],f[d]+f[i-2]);
            if(d>=3) f[x]=min(f[x],f[d-2]+f[i]);
        }
    }
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n;
        if(f[n]>=ee) cout<<"-1\n";
        else cout<<f[n]<<"\n";
    }
    return 0;
}

::::