题意：
有一棵大小为 \(n\) 的无标号无根树，其中有三种结点：红蓝黄。
红色结点的度数最多为 \(4\)，蓝、黄结点的度数最多为 \(3\)。
黄色结点之间不能有直接连边。
问方案数，\(\bmod~998244353\)，\(n\le10000\)。
思路：
无根树同构问题，一般是转化为以重心为根，然后按照有根树来做，这道题也是这样。
我们先考虑一个 \(O(n^3)\) 的 暴力解法，每次我们枚举根的度数和颜色，每个子树的大小。
然后我们发现，对于大小相同的子树，实际上方案数也是相同的，这就启发我们对子树的大小进行 DP。
我们令 \(f_{0/1/2,~i}\) 表示当根是红/蓝/黄，子树大小为 \(i\) 时，方案数是多少。
显然这很难直接转移，因此我们还要定义两个数组：
\(rb_{d,~i}\) 表示根的度数为 \(d=0/1/2/3/4\)，子树大小为 \(i\) 的方案数，且此时根应为红色或蓝色（其实当 \(d=4\) 就特指根为红色）。
\(ye_{d,~i}\) 表示根的度数为 \(d=0/1/2/3\)，子树大小为 \(i\) 的方案数，且此时根的颜色应为黄色。
假设此时我们处理到子树大小为 \(i\) 的情况，
首先我们先更新 \(f\) 数组：
\[f_{0,~i}=\sum_{d=0}^3 rb_{d,~i} \]\[f_{1,~i}=\sum_{d=0}^2 rb_{d,~i} \]\[f_{2,~i}=\sum_{d=0}^2 ye_{d,~i} \]为什么 \(f\) 不能更新满呢？因为我们要用 \(f\) 去更新 \(rb,ye\)，那么要求 \(f\) 里的方案数都至少能再连出一条边。
这时候我们已经计算完大小为 \(i\) 的不同子树的方案数，我们就可以去更新 \(rb,ye\) 数组：
我们以更新 \(rb\) 为例，假设要更新 \(rb_{j,z}\)：
我们枚举选出 \(w\) 个大小为 \(i\) 的子树，方案数显然为 \(\begin{pmatrix} tot+w-1 \\ w \end{pmatrix}\)
其中 \(tot=f_{0,i}+f_{1,i}+f_{2,i}\)
那么就有转移：
\[f_{j,z}\leftarrow f_{j-w, z-i*w} \times \begin{pmatrix} tot+w-1 \\ w \end{pmatrix} \]\(ye\) 数组的更新同理，不过要注意 \(tot=f_{0,i}+f_{1,i}\)，因为黄色不能与黄色连边。
因为重心的子树的大小不超过 \(\lfloor \frac{n}{2} \rfloor\)，因此我们的 \(f\) 只需要更新到 \(\lfloor \frac{n}{2} \rfloor\)。
最后我们用 \(rb_{d,n}\) 和 \(ye_{d,n}\) 来计算最终的答案。
但有一个细节：对于 \(n\) 为偶数的情况，可能会出现两个重心的情况（就是某一条边连接的两棵子树大小都为 \(\frac{n}{2}\)），这时候我们需要去重。
一些具体细节见代码。
代码
#include<bits/stdc++.h>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
namespace MOD
{
int mod;
inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
inline int fast_pow(int a, int b = mod - 2)
{
int re = 1;
while(b)
{
if(b & 1) re = mul(re, a);
a = mul(a, a);
b >>= 1;
}
return re;
}
} using namespace MOD;
int n, f[3][3005], inv[5];
int rb[5][3005], ye[4][3005];
int C[5];
signed main()
{
n = rd(), mod = rd();
inv[1] = 1; FOR(i, 2, 4) inv[i] = mul(sub(mod, mod / i), inv[mod % i]);
rb[0][1] = ye[0][1] = 1;
FOR(i, 1, n >> 1)
{
FOR(j, 0, 2)
f[0][i] = add(f[0][i], rb[j][i]),
f[1][i] = add(f[1][i], rb[j][i]),
f[2][i] = add(f[2][i], ye[j][i]);
f[0][i] = add(f[0][i], rb[3][i]);
// 更新 ye
int tot = add(f[0][i], f[1][i]);
C[1] = tot;
FOR(j, 2, 3) C[j] = mul(C[j - 1], mul(tot + j - 1, inv[j]));
ROF(j, 3, 1) ROF(z, n, i + 1) for(int w = 1, mx = z / i; w <= mx && w <= j; w++)
ye[j][z] = add(ye[j][z], mul(ye[j - w][z - i * w], C[w]));
// 更新 rb
tot = add(tot, f[2][i]);
C[1] = tot;
FOR(j, 2, 4) C[j] = mul(C[j - 1], mul(tot + j - 1, inv[j]));
ROF(j, 4, 1) ROF(z, n, i + 1) for(int w = 1, mx = z / i; w <= mx && w <= j; w++)
rb[j][z] = add(rb[j][z], mul(rb[j - w][z - i * w], C[w]));
}
int ans = 0;
FOR(i, 0, 3) ans = add(ans, add(mul(rb[i][n], 2), ye[i][n]));
ans = add(ans, rb[4][n]);
if(!(n & 1)) // 有两个重心时，需要去重
{
int t = add(f[0][n >> 1], f[1][n >> 1]);
if(t & 1) t = add(mul(t, (t - 1) >> 1), mul(t, f[2][n >> 1]));
else t = add(mul(t - 1, t >> 1), mul(t, f[2][n >> 1]));
ans = sub(ans, t);
}
printf("%d", ans);
return 0;
}
GJ 那里需要开火车头才能通过；
Luogu 原题的范围是 \(n\le 3000\) 的，大家可以到那里去提交一下。
标签：子树,int,ye,rb,mul,旅伴,2022.10,mod From： https://www.cnblogs.com/zuytong/p/16793571.html