【UOJ 351】新年的叶子 / 题解

题目描述

对于一颗树，每次随机选择一个叶子，将其染黑，经过无数次操作以后，所有叶子将变成黑色。求期望在这之前的哪一时刻，不包含黑色点的直径长度第一次变小？

思路

首先我们找到这棵树的直径。如果直径长度是偶数，所有直径必有一个必经点，这个点为中点；如果直径长度是奇数，所有直径必有一条必经边，这条边也在直径的正中间。

我们沿着必经点或者必经边切开，能把树分成若干个集合，每个集合中有一些叶子是直径可能的端点。直径长度变小，当且仅当除剩下的一个集合外，所有集合中可能作为直径端点的叶子均被染黑。

于是我们可以枚举剩下哪个集合没有被全部染黑，分别计算贡献，最后容斥一下得出答案。

代码

#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; pre[maxn],deg[maxn],inv[maxn],chain,ans,x,y,s; void init(){ inv[1]="1;" for (register i="2;i<=n;++i)" inv[i]="(1ll*(md-md/i)*inv[md%i]%md+md)%md;" } add(int a,int b){ l[++cnt]="Edge(b,head[a]);" head[a]="cnt;deg[b]++;" 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