CF2112E Tree Colorings 题解

思路

首先考虑一个类似的问题如何解决：给定一棵树，求这棵树美丽的染色方案数。这个问题可以用一个树形 DP 解决。

首先，有一个性质。整棵树被分成了几个同颜色的连通块：包含根节点的绿色连通块，其余的子树要么全染黄，要么全染蓝。这样才可以满足这几个条件。所以设

dp_u

代表以

u

为根的子树中美丽染色的方案数。那就从

v \in son_u

向

u

转移。每一次有

3

种情况：保留以

v

为根的子树不变、全染黄、或全染蓝。所以：

dp_u = \prod_{v \in son_u} (dp_v + 2)

其中叶子节点的

dp_u = 1

。我们发现所有

dp_u

一定为奇数（因为

+2

不改变奇偶性），所以当且仅当

u \equiv 1 \pmod 2

，才会有答案，否则输出 -1。

回到原问题，设

f_i

代表美丽染色方案数恰好为

i

的有根树节点的最小值。那我们可以考虑将两棵子树合并。由上面的问题可知如果第一棵子树的方案数为

i

，第二棵子树的方案数为

j

，则这棵树就有

(i + 2)(j + 2)

种方案数。那我们直接枚举其中一棵子树转移即可：

f_i = \min_{j|i,1 < j < i}(f_j + f_{\frac{i}{j} - 2})

其中

j

代表其他的方案，

\displaystyle \frac{i}{j}

为枚举的那棵子树的大小。因为需要

1 \sim m

的所有因数，可以用

CPP

for (int i = 1; i <= m; i++)
		for (int j = i; j <= m; j += i)
			fact[j].push_back(i);

求出

1 \sim m

的每一个数的所有因数。时间复杂度

\sum \limits_{i=1}^n \displaystyle \frac {n}{i} \approx \mathcal{O}(n \log n)

。

预处理

f

，最终时间复杂度为

\mathcal{O}(n \log n + t)

。

代码

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int t, m;
int f[N];
vector<int> fact[N];

int main()
{
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i < N; i += 2)
		for (int j = i; j < N; j += i)
			fact[j].push_back(i);
	f[0] = 0, f[1] = 1;
	for (int i = 3; i < N; i += 2)
		for (int j : fact[i])
			f[i] = min(f[i], f[j] + f[(i / j) - 2]);
	scanf("%d", &t);
	while (t--)
	{
		int m;
		scanf("%d", &m);
		if (f[m] <= 1e9) printf("%d\n", f[m]);
		else printf("-1\n");
	}
	return 0;
}

CF2112E Tree Colorings 题解

文章操作

思路

代码

相关推荐

评论

CF2112E Tree Colorings 题解