[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

即可。

时间复杂度调和级数级。

code

CPP

#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;
}

[CF2112E] Tree Colorings 题解

文章操作

相关推荐

评论

[CF2112E] Tree Colorings 题解