题目描述
对于一颗树，每次随机选择一个叶子，将其染黑，经过无数次操作以后，所有叶子将变成黑色。求期望在这之前的哪一时刻，不包含黑色点的直径长度第一次变小？
思路
首先我们找到这棵树的直径。如果直径长度是偶数，所有直径必有一个必经点，这个点为中点；如果直径长度是奇数，所有直径必有一条必经边，这条边也在直径的正中间。
我们沿着必经点或者必经边切开，能把树分成若干个集合，每个集合中有一些叶子是直径可能的端点。直径长度变小，当且仅当除剩下的一个集合外，所有集合中可能作为直径端点的叶子均被染黑。
于是我们可以枚举剩下哪个集合没有被全部染黑，分别计算贡献，最后容斥一下得出答案。
代码
#include
#define maxn 500500
#define md 998244353
#define ll long long
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1];
int head[maxn],f[maxn],q[maxn],t,leaf,cnt,tot,n,nod;
int pre[maxn],deg[maxn],inv[maxn],chain,ans,X,Y,S;
void Init(){
inv[1]=1;
for (register int i=2;i<=n;++i)
inv[i]=(1ll*(md-md/i)*inv[md%i]%md+md)%md;
}
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;deg[b]++;
}
void Dfs(int u,int fa,int dis){
if (dis>chain) chain=dis,nod=u;
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa) continue;
pre[v]=u,Dfs(v,u,dis+1);
}
}
void Sum(int u,int fa,int dis){
if (dis==chain/2) tot++;
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa) continue;
Sum(v,u,dis+1);
}
}
int main(){
scanf("%d",&n);Init();
for (register int i=1,a,b;i