【DP】【CF855C】 Helga Hufflepuff's Cup

Description

给你一个树，可以染 \(m\) 个颜色，定义一个特殊颜色 \(k\) ，要求保证整棵树上特殊颜色的个数不超过 \(x\) 个。同时，如果一个节点是特殊颜色，那么它的相邻节点的颜色编号必须全部小于 \(k\)。求方案数。

Input

第一行 \(n,m\) 代表节点个数和颜色树

下面 \(n~-~1\) 行描述一棵树

最后一行是特殊颜色 \(k\) 和颜色个数 \(x\)

Output

输出一行一个整数，代表答案对 \(10^9~+~7\) 取模结果

Hint

\(Forall:\)

\(n~\leq~10^5~,~m~\leq~10^9~,~k~\leq~m~,~x~\leq~10\)

Solution

这题感觉有点像DDOSvoid的疑惑

我爆破我自己

数数题，考虑DP。

显然这个题的选点分为三种，分别是小于 \(k\)，等于 \(k\)，大于 \(k\)。同时有颜色个数的限制，于是可以设 \(f_{i,j,0/1/2}\) 代表以 \(i\) 为根的子树，选了 \(j\) 个特殊颜色，其中节点 \(i\) 的颜色小于/等于/大于 \(k\)

考虑一个节点只有两个儿子的情况，直接把贡献乘一下即可。

考虑一个节点有多个儿子的时候，每加入一个新节点产生的贡献如何计算：

设 \(g_{i,j,0/1/2}\) 为 \(u\) 的子树（省略第一维），考虑前 \(i\) 个儿子，选了 \(j\) 个 \(k\)，节点 \(i\) 的状态是 \(0/1/2\) 的方案数。

一下假设当前枚举的是 \(u\) 的第 \(i\) 个儿子。

考虑 \(u\) 选小于 \(k\) 的情况：

则该儿子可以选 \(0/1/2\) 三种情况，这三种情况相互并行，应该将贡献相加，同时两两子树间互不影响，应将贡献相乘。

于是有

\[g_{i,j,0}~=~\sum_{h=0}^{j}(g_{i-1,j-h,0}~\times~\sum_{s=0}^{2}f_{to,h,s})
\]

同理，\(u\) 选等于 \(k\) 的情况：

该儿子只能选 \(0\) 一种情况，于是有

\[g_{i,j,1}~=~\sum_{h=0}^{j}(g_{i-1,j-h,1}~\times~f_{to,h,0})
\]

同理，\(u\) 选大于 \(k\) 的情况：

该儿子可以选 \(0/2\) 两种可能，于是

\[g_{i,j,2}~=~\sum_{h=0}^{j}(g_{i-1,j-h,2}~\times~\sum_{s=0,2}f_{to,h,s})
\]

设 \(u\) 有 \(v\) 个孩子，于是

\[f_{u,j,0/1/2}~=~g_{v,j,0/1/2}
\]

当然 \(g\) 可以把第一维滚掉，这样就没有空间问题辣~

于是就可以统计答案了。记得取模。代码里面因为不知道哪里爆掉了于是干脆 \(define~~int~~ll\) 了23333

Code

#include <cstdio>

#include <cstring>

#ifdef ONLINE_JUDGE

#define freopen(a, b, c)

#endif

#define rg register

#define ci const int

#define cl const long long

#define int ll

typedef long long ll;

namespace IPT {

	const int L = 1000000;

	char buf[L], *front=buf, *end=buf;

	char GetChar() {

		if (front == end) {

			end = buf + fread(front = buf, 1, L, stdin);

			if (front == end) return -1;

		}

		return *(front++);

	}

}

template <typename T>

inline void qr(T &x) {

	rg char ch = IPT::GetChar(), lst = ' ';

	while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();

	while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();

	if (lst == '-') x = -x;

}

template <typename T>

inline void ReadDb(T &x) {

	rg char ch = IPT::GetChar(), lst = ' ';

	while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();

	while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();

	if (ch == '.') {

		ch = IPT::GetChar();

		double base = 1;

		while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();

	}

	if (lst == '-') x = -x;

}

namespace OPT {

	char buf[120];

}

template <typename T>

inline void qw(T x, const char aft, const bool pt) {

	if (x < 0) {x = -x, putchar('-');}

	rg int top=0;

	do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);

	while (top) putchar(OPT::buf[top--]);

	if (pt) putchar(aft);

}

const int maxn = 100010;

const int maxm = 200010;

const int MOD = 1000000007;

struct Edge {

	int to, nxt;

};

Edge edge[maxm]; int hd[maxn], ecnt = 1;

inline void cont(ci from, ci to) {

	Edge &e = edge[++ecnt];

	e.to = to; e.nxt = hd[from]; hd[from] = ecnt;

}

int n, m, x, v, dv;

int frog[maxn][15][3], gorf[maxn][2][15][3];

void reading();

void dfs(ci, ci);

signed  main() {

	freopen("1.in", "r", stdin);

	qr(n); qr(m);

	reading();

	qr(v); qr(x); dv = m - v;

	dfs(1, 0);

	int ans = 0;

	for (rg int i = 0; i <= x; ++i)

		for(rg int j = 0; j < 3; ++j) ans = (ans + frog[1][i][j]) % MOD;

	qw(ans, '\n', true);

	return 0;

}

void reading() {

	int a, b;

	for (rg int i = 1; i < n; ++i) {

		a = b = 0;

		qr(a); qr(b);

		cont(a, b);

		cont(b, a);

	}

}

void dfs(ci u, ci pree) {

	int pre = 0;

	gorf[u][pre][0][0] = v - 1;

	gorf[u][pre][1][1] = 1;

	gorf[u][pre][0][2] = dv;

	for (int i = hd[u]; i; i = edge[i].nxt) if(i != pree) {

		int &to = edge[i].to;

		dfs(to, i ^ 1);

		pre ^= 1;

		memset(gorf[u][pre], 0, sizeof gorf[u][pre]);

		for (rg int j = 0; j <= x; ++j) {

			for (rg int k = 0; k <= j; ++k) {

				gorf[u][pre][j][0] = (gorf[u][pre][j][0] + 1ll * gorf[u][pre ^ 1][j - k][0] * (frog[to][k][0] + frog[to][k][1] + frog[to][k][2])) % MOD;

				gorf[u][pre][j][1] = (1ll * gorf[u][pre ^ 1][j - k][1] * frog[to][k][0] + gorf[u][pre][j][1]) % MOD;

				gorf[u][pre][j][2] = (1ll * gorf[u][pre ^ 1][j - k][2] * (frog[to][k][0] + frog[to][k][2]) + gorf[u][pre][j][2]) % MOD;

			}

		}

	}

	for (rg int i = 0; i <= x; ++i)

		for (rg int j = 0; j < 3; ++j)

			frog[u][i][j] = gorf[u][pre][i][j];

#ifdef DEBUG

	printf("EM%d:\n", u);

	for (rg int i = 0; i <= x; ++i) {

		for (rg int j = 0; j < 3; ++j)

			printf("%d %d %d\n",i, j, frog[u][i][j]);

	}

#endif

}

Summary

这类树上求方案数的问题都需要在转移时借助一个辅助数组，记录已经枚举过得儿子的信息，然后计算当前这个儿子加入的贡献。

巴特西