原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ351.html
题目传送门 - UOJ351
题意
有一个 n 个节点的树，每次涂黑一个叶子节点（度为 1 的节点），可以重复涂黑。
问使得白色部分的直径发生变化的期望涂黑次数。
$n\leq 5\times 10^5$
题解
首先考虑什么情况下直径长度会发生改变。
考虑找到直径的中点，可能在边上。
对于这个直径相连的每一个子树，分别算出在这个子树中的距离直径中点距离为直径长度的一半的节点个数。
于是我们就得到了一些集合。那么，直径长度将在 只剩下一个集合有白色节点 的时候发生改变。
于是，很容易得出菊花图的做法：
$$ ans = \sum_{i=1}^{n-1} \frac {n-1} {n-i}$$
但是不是菊花图的时候，仍然很棘手。
设总叶子节点个数为 $l$ ，所有集合的元素个数总和为 $tot$ 。
官方题解的算法三应该比较好理解吧
算法三
我们考虑枚举哪个集合最终剩下了，设当前集合大小为 $k$ 。
设所有集合大小的和为 $n$ 。
我们枚举当其他所有集合都染黑时，当前集合还剩下 $i$ 个没有被染黑，那么这样的情况对答案的贡献为
$$\frac{\binom{k}{i}\times \binom{n-i-1}{n-k-1}\times \binom{n-k}{1}\times(k-i)!\times(n-k-1)!\times (i)!}{n!}\times (\sum_{j=i+1}^{n}\frac{m}{j})$$
线性预处理阶乘，阶乘逆元与逆元的前缀和就可以做到 $O(n)$ 的时间复杂度。
算法四比较神仙
算法四
from WuHongxun
http://wuhongxun.blog.uoj.ac/blog/3345
放链接（逃
对于算法四，我再补充一句：
考虑任何一个方案里我们染黑到所有集合都变黑了为止，它对答案的贡献是多少呢？如果 x 是这个方案里最后被染黑的集合，那么是倒数第二个被染黑的时间，反之则是最后一个集合被染黑的时间。
这里，如果 x 不是最后一个被染黑的集合，那么必然全部染黑了。
代码
1#include <bits/stdc++.h> 2using namespace std; 3int read(){ 4 int x=0; 5 char ch=getchar(); 6 while (!isdigit(ch)) 7 ch=getchar(); 8 while (isdigit(ch)) 9 x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 10 return x; 11} 12const int N=500005,mod=998244353; 13int n; 14vector <int> e[N],S; 15int in[N],depth[N],fa[N]; 16int vis[N]; 17void dfs(int x,int pre,int d){ 18 depth[x]=d,fa[x]=pre; 19 for (auto y : e[x]) 20 if (y!=pre) 21 dfs(y,x,d+1); 22} 23int LCA(int x,int y){ 24 if (depth[x]<depth[y]) 25 swap(x,y); 26 while (depth[x]>depth[y]) 27 x=fa[x]; 28 while (x!=y) 29 x=fa[x],y=fa[y]; 30 return x; 31} 32int FindFar(int x,int d){ 33 vis[x]=d; 34 int res=x; 35 for (auto y : e[x]) 36 if (!~vis[y]){ 37 int tmp=FindFar(y,d+1); 38 if (vis[tmp]>vis[res]) 39 res=tmp; 40 } 41 return res; 42} 43void Get(int x,int d,int md){ 44 if (d==md) 45 S.back()++; 46 vis[x]=1; 47 for (auto y : e[x]) 48 if (!vis[y]) 49 Get(y,d+1,md); 50} 51void Get_S(){ 52 memset(vis,-1,sizeof vis); 53 int s=FindFar(1,0); 54 memset(vis,-1,sizeof vis); 55 int t=FindFar(s,0); 56 if (depth[s]<depth[t]) 57 swap(s,t); 58 int d=depth[s]+depth[t]-2*depth[LCA(s,t)]; 59 memset(vis,0,sizeof vis); 60 if (d&1){ 61 for (int i=d/2;i--;) 62 s=fa[s]; 63 t=fa[s]; 64 vis[s]=vis[t]=1; 65 S.push_back(0),Get(s,0,d/2); 66 S.push_back(0),Get(t,0,d/2); 67 } 68 else { 69 for (int i=d/2;i--;) 70 s=fa[s]; 71 vis[s]=1; 72 for (auto y : e[s]) 73 S.push_back(0),Get(y,1,d/2); 74 } 75} 76int Pow(int x,int y){ 77 int ans=1; 78 for (;y;y>>=1,x=1LL*x*x%mod) 79 if (y&1) 80 ans=1LL*ans*x%mod; 81 return ans; 82} 83int Fac[N],Inv[N],Iv[N],h[N]; 84void Math_Prework(){ 85 for (int i=Fac[0]=1;i<=n;i++) 86 Fac[i]=1LL*Fac[i-1]*i%mod; 87 Inv[n]=Pow(Fac[n],mod-2); 88 for (int i=n;i>=1;i--) 89 Inv[i-1]=1LL*Inv[i]*i%mod; 90 for (int i=1;i<=n;i++) 91 Iv[i]=1LL*Inv[i]*Fac[i-1]%mod; 92 for (int i=1;i<=n;i++) 93 h[i]=(h[i-1]+Iv[i])%mod; 94} 95int C(int n,int m){ 96 if (m<0||m>n) 97 return 0; 98 return 1LL*Fac[n]*Inv[m]%mod*Inv[n-m]%mod; 99} 100int main(){ 101 n=read(); 102 for (int i=1;i<n;i++){ 103 int a=read(),b=read(); 104 e[a].push_back(b); 105 e[b].push_back(a); 106 in[a]++,in[b]++; 107 } 108 dfs(1,0,0); 109 Get_S(); 110 int l=0; 111 for (int i=1;i<=n;i++) 112 if (in[i]==1) 113 l++; 114 Math_Prework(); 115 int tot=0; 116 for (auto y : S) 117 tot+=y; 118 // 设当前剩余 k 个，总共有 l 个，选出 x 个数： 119 // l/k + l/(k-1) + ... + l/(k-x+1) 120 // l * (h[k]-h[k-x]) 121 int ans=0; 122 for (auto y : S) 123 ans=(1LL*h[tot-y]+ans)%mod; 124 ans=(-1LL*((int)S.size()-1)*h[tot]%mod+ans+mod)%mod; 125 ans=1LL*ans*l%mod; 126 printf("%d",ans); 127 return 0; 128}