雷州新年餅的葉子叫什么，【UOJ #351】新年的葉子（樹的直徑，期望）

題目鏈接

這的確是一道好題，我們不妨依循思路一步步推導，看問題是如何被解決的。

雷州新年餅的葉子叫什么、做一些約定，設$m$為樹的葉子節點個數，設$len$為該樹的直徑（經過的點數）。

毫無疑問，直徑可能有多條，我們需要把所有直徑都破壞掉才能終止，但這些直徑并不是毫無聯系的。

引理：若$len$為奇數，則所有直徑有同一個中點；若$len$為偶數，則所有直徑有同一條最中間的邊。

• 至于證明，用反證法即可，大致就是如果存在兩條直徑的中點不是同一個，那就會產生更長的一條直徑。

一棵完全二叉樹有2021個葉子節點、題目要求的終止狀態就是不存在兩個可以構成直徑的點，可以構成直徑的點指的是原先處在某一條直徑的兩端的點，我們可以先按$len$的奇偶討論：

1. 若$len$為奇數，即存在一個中點$x$，我們不妨將$x$設成根，不難發現，如果兩個點$a,b$的$lca$是$x$，那$a,b$就能構成直徑，否則就不能。這啟發我們把所有可以構成直徑的點，按照他們在$x$的哪個親兒子下分組，那樣同一個組內的點互相不能構成直徑，不在一個組內的兩點能構成直徑。
2. 若$len$為偶數，即所有直徑都會經過中間兩個點，我們模仿之前的思路，從這兩個點之間分開，把這些可以構成直徑的點分成的兩個組，道理同上。

這樣我們得到了若干個點的集合，假設我們得到了$t$個集合，其集合大小用$k$表示，所有集合大小之和用$sum$表示，并且我們只關心集合的大小，集合中具體有那些點并不重要。然后我們發現，如果存在兩個集合都沒有被完全染黑，原先的直徑還是存在的，也就是說我們第一次使得只剩下一個集合沒有被完全染黑的時間就是我們所希望的。

我們按照這個精簡后的題目做，這里有兩種做法，分別從兩個不同角度求解。

法一：

在此之前，我們必須先明白一件事，期望實際上是若干個隨機事件的概率乘上該事件的價值的和。

我們知道經過無限次染色后所有葉子終究都會被染黑，而每一種染黑的方案中這些葉子被染黑是有順序的，由于每次染色都是隨機的，所以產生每一種順序的概率是均等的，但是不同的順序會導致它們終止的時間不同。所以這個做法總體上是把所有事件按照點染黑的順序分組分別算，最后把貢獻加起來。

有諸多順序它們的期望步數是相等的，我們會把它們合起來算。我們枚舉一個集合，將它作為最后那個沒有被完全染黑的集合，并枚舉這個集合在終止時有多少個點已經被染黑了，顯然所有滿足以此為終止狀態的順序的期望步數都是一樣的。這里要注意的是，染黑的最后一個點一定是其它集合中的點，這是需要特殊考慮的。

于是我們可以寫出貢獻和的表達式：

$$ans = \frac{1}{sum!} \sum_{i = 1}^{t} \sum_{j = 0}^{k_i - 1} \tbinom{k_i}{j} (m - k_i) (m - k_i + j - 1)! (k - j)! \sum_{z = k_i - j + 1}^{sum} \frac{m}{z}$$

這里可能有些需要解釋的地方，就是為什么這么算是對的，這可能一開始看會覺得難以理解。你會發現對于每一個順序而言，我們讓$\sum_{z} \frac{m}{z}$成為它的貢獻的行為令人費解，因為這個式子在做的東西是無序的，并沒有按照我們所想的順序染色。但是每個順序的概率是均等的，我們僅僅只需要這個期望式子中的一部分，只要把$sum!$除掉就可以了。

法二：

既然我們要算的是所有合法事件的概率乘貢獻之和（這里所說的合法事件指第一次使得只剩下一個集合沒有被完全染黑，因為只有這些是被算進答案里的），用容斥也是可以得到的。

如果我們枚舉一個集合$i$，想要讓$i$成為最后那個沒有被完全染黑的集合，我們算出只關心其余集合的點把它們染黑的期望時間。在這個期望中，每一種方案的最后一個染色的點一定不在$i$中。這里有兩種情況，一種是在染色結束時$i$中仍存在沒染黑的點，這屬于合法情況；另一種是$i$中的點已經全部被染黑了，也就是所有點都沒染黑了，這是需要去掉的。我們考慮每一種全部染黑的方案會在除了最后染色的集合外的其他$t-1$個集合中都被算到，所以最終的答案就是枚舉每個集合算其余點被染黑的期望時間減去$t-1$倍的把所有點都染黑的期望時間。

我們發現這么容斥后，剩下的事件的概率和恰好是$1$，單純從概率分支樹上來講肯定是對的。具體來講就是一種全部染黑的方案事實上是一種合法方案的一個分支，本來就不應該算進去，而合法事件顯然是不重復不遺漏的。

?

這是法二的實現：

#include <cstdio>
#include <algorithm>using namespace std;typedef long long LL;const int N = 500005;
const int MOD = 998244353;int n, m, bt, len, su, ans, tmp;
int bl[N], inv[N], sui[N], dep[N], fa[N], deg[N];int yu, la[N], to[N << 1], pr[N << 1];
inline void Ade(int a, int b) {to[++yu] = b, pr[yu] = la[a], la[a] = yu;
}void Dfs(int x, int fat, int &c) {dep[x] = dep[fa[x] = fat] + 1;if (dep[x] == len / 2) ++c;for (int i = la[x]; i; i = pr[i])if (to[i] != fat) Dfs(to[i], x, c);
}inline int Add(int a, int b) {return (a += b) >= MOD? a - MOD : a;
}int main() {scanf("%d", &n);for (int i = 1, x, y; i < n; ++i) {scanf("%d%d", &x, &y);Ade(x, y), Ade(y, x);++deg[x], ++deg[y];}Dfs(1, 0, tmp);int rt = 1, tl = 1;for (int i = 1; i <= n; ++i) {if (dep[i] > dep[rt]) rt = i;if (deg[i] == 1) ++m;}Dfs(rt, 0, tmp);for (int i = 1; i <= n; ++i)if (dep[i] > dep[tl]) tl = i;len = dep[tl];inv[1] = 1, sui[1] = m;for (int i = 2; i <= n; ++i) {inv[i] = MOD - (LL)MOD / i * inv[MOD % i] % MOD;sui[i] = Add(sui[i - 1], (LL)m * inv[i] % MOD);}if (len & 1) {int md = -1;for (int i = tl; i; i = fa[i])if (dep[i] == (len + 1) / 2) md = i;dep[md] = 0;for (int i = la[md]; i; i = pr[i]) {Dfs(to[i], md, tmp = 0);if (tmp) bl[++bt] = tmp, su += bl[bt];}} else {int m1 = -1, m2 = -1;for (int i = tl; i; i = fa[i]) {if (dep[i] == len / 2) m1 = i;if (dep[i] == len / 2 + 1) m2 = i;}dep[m2] = 0, Dfs(m1, m2, bl[++bt]);dep[m1] = 0, Dfs(m2, m1, bl[++bt]);su = bl[1] + bl[2];}for (int i = 1; i <= bt; ++i)ans = Add(ans, sui[su - bl[i]]);ans = Add(ans, MOD - (bt - 1LL) * sui[su] % MOD);printf("%d\n", ans);return 0;
}

?