久远是迷途里酝酿的酒，愈陈愈香
ARC140D One to One
首先挖掘性质，图只有可能是环，基环树，树三种情况，注意到有 $-1$ 的一定是树的情况（且可以注意到每棵树只有一个 $-1$)，并且在确定了 $-1$ 之后，一定会变成前面两种情况。
考虑把所有的树先取出来。注意到我们可以通过计算每种连通块出现的方案数来计算答案。（注意这里的每种是指若干个树连通块连在一起构成的环或基环数。）
令人疑惑的 DP：定义 $dp_{i,j}$ 表示将前 $i$ 个树连通块，选择 $j$ 个合并为一个连通块的方案数。
考虑如果我们知道 $j$ 个连通块分别是什么，那么方案数应该是 $[(\sum_{i=1}^j \text{siz}_i)-1]!\times \prod_{i=1}^j \text{siz}_i$。（可以理解找到一个排列，每次从 $i\to i \bmod j +1$ 连通块连一条边，注意到是圆排列，所以要 $-1$。）
然后，我们就有了转移式：$dp_{i,j}=dp_{i-1,j-1}\times \text{siz}_i \times \max(j-1,1)+dp_{i-1,j}$。
考虑如何统计答案，首先对于环和基环树，显然直接让答案加上 $n^m$。（其中 $m$ 表示树的连通块的数量）
考虑对于树所构成的连通块，那么应该是 $\sum _{i=1}^m dp_{m,i}\times n^{m-i}$。（因为剩下的可以乱连，无论怎么连都不会影响这个连通块的存在性。）
时间复杂度 $\mathcal{O}(n^2)$。
CF724F Uniformly Branched Trees
把握三个点，钦定根为重心。
- 限制子树大小 $\le \frac{n}{2}$
- 一个一个分离子树时，钦定后面的子树小于分离的子树来实现去重，对于子树大小相同的，一起处理。
- 双重心会出事 ，你可能会算重。记得在 $n$ 为偶数的时候，剪掉双重心的重复方案。
细节见极丑无比的代码。（然后还要注意 $n=2$ 的 $\text{Corner case}$。而且代码常数太大疑似被卡了）
时间复杂度 $\mathcal{O}(n^2d^2)$。 （Upd：我这个复杂度假了，但是应该能方便理解。）
int dp[1005][15][1005];
int fact[15], inv[15];
int dfs(int x, int d, int lim)
{
if(!d && x == 1) return true;
if(!d) return 0;
if(x == 1) return 1;
if(~dp[d][lim]) return dp[d][lim];
int now = 0;
for (int i = 1; i <= lim && i < x; ++i)
{
int qwq = -1, all = 1;
for (int j = 1; j <= d; ++j)
{
if(x - i * j - bool(d - j) > 0)
{
if(qwq == -1) qwq = dfs(i, ::d - 1, lim);
all = 1ll * all * qwq % mod;
++qwq;
now += 1ll * all * inv[j] % mod * dfs(x - i * j, d - j, i - 1) % mod, now %= mod;
}
else break;
}
}
return dp[d][lim] = now;
}
int main()
{
cin >> n >> d >> mod;
if(n <= 2) return puts("1"), 0;
fact[0] = 1;
for (int i = 1; i <= d; ++i) fact[i] = fact[i - 1] * 1ll * i % mod;
for (int i = 0; i <= d; ++i) inv[i] = ksm(fact[i], mod - 2);
memset(dp, -1, sizeof(dp));
int ans = dfs(n, d, n / 2);
if(n & 1) cout << ans << endl;
else
{
int qwq = dfs(n / 2, d - 1, n / 2);
ans = (ans - 1ll * qwq * (qwq - 1) / 2 % mod + mod) % mod;
cout << ans << endl;
}
return 0;
}
「KDOI-06-S」树上异或
首先有一个 $\mathcal{O}(nV^2)$ 的暴力树上背包做法，看能不能给我们一些启发。
注意到异或，考虑拆位，即定义 $dp_{i,j,k}$ 表示 $i$ 所在连通块当前异或和的第 $j$ 位为 $k$ 的异或和之积。
两种转移：
- $dp_{i,j,k_1\oplus k_2}+dp_{i,j,k_1}\times dp_{\text{son},j,k_2}\to dp_{i,j,k_1\oplus k_2}$。此时只是单纯合并连通块，没有对答案造成新贡献，所以这样写没问题。
- $dp_{i,j,k}\times dp_{i,j' \in [0\to \log V],1}\times 2^{j'}\to dp_{i,j,k}$。注意断开边时，要把所有二进制位的答案都加上。（用分配率拆一下可以发现这样写是没有问题的。）
第二个转移预处理一下 $dp_{i,j' \in [0\to \log V],1}\times 2^{j'}$ 的总和，应该可以做到 $\mathcal{O}(n\log V)$。
答案是 $\sum_{i=0}^{\log V} dp_{1,i,1}\times 2^i$。
[SHOI2012] 随机树
给我一种我不知道概率期望是什么感觉。
第一问，定义 $dp_i$ 表示有 $i$ 个叶子的期望平均深度。
注意到展开是随机的，有 $dp_i=\frac{dp_{i-1}\times i+2}{i}$。
第二问，考虑期望转概率。
定义 $dp_{i,j}$ 表示当前有 $i$ 个叶子，深度 $\ge j$ 的概率是多少。
考虑枚举左右子树进行转移：
有 $dp_{i,j}=\frac{1}{i-1}\times \sum_{k-1}^{i-1}(dp_{k,j-1}\times 1+dp_{i-k,j-1}\times 1-dp_{k,j-1}\times dp_{i-k,j-1})$
一个简单的容斥。为什么要 $\frac{1}{i-1}$，见此。
